Structure de données pour contenir et récupérer des points dans un plan

Question

Définition 1: Point $ (x, y) $ contrôle le point $ (x ', y') $ si et seulement si $ x <x '$ et $ y <y' $.

Définition 2: Point $ (x, y) $ est contrôlé par le point $ (x ', y') $ si et seulement si $ x '<x $ et $ y' <y $.

J'essaie de proposer une structure de données pour soutenir les opérations suivantes:

• $ mathrm {add} (x, y) $ - ajoute un point $ (x, y) $ au système dans $ mathcal {o} ( log n) $ complexité où $ n $ est le nombre de points dans le système.

• $ mathrm {supprimer} (x, y) $ - supprime un point $ (x, y) $ du système dans $ mathcal {o} ( log n) $ complexité où $ n $ est le nombre de points dans le système.

• $ mathrm {score} (x, y) $ - Renvoie le nombre de points $ (x, y) $ contrôle - nombre de points que $ (x, y) $ est contrôlé par. Pire complexité de cas $ mathcal {o} ( log n) $.

---

J'ai essayé de le résoudre en utilisant plusieurs arbres AVL, mais je n'ai pas pu trouver une solution suffisamment élégante.

Cette question est apparue à mes examens il y a quelques jours. La question devrait avoir relativement simple car elle valait 15 $ / 100 $ de points. J'ai essayé de résoudre ce problème par plusieurs arbres AVL mais je n'ai pas pu trouver une solution suffisamment élégante.

Les conseils sont les bienvenus.