algorithm - 维护数字的数据结构

Question

请建议一种数据结构来维护数字，以便我可以回答以下查询 -

查找(int n) - O(log(n))

统计小于 k = O(log(n)) 的数

插入 - O(Log(n))

这不是家庭作业，而是我为了解决更大的问题而遇到的一个小问题 - Number of students with better grades and lower jee rank

我有一个 avl 树，每个节点都维护子树中的节点数。但是我不知道如何在完成插入和重新平衡时在每个节点上维护这个计数。

Answer 1

我也会尝试使用 AVL 树。如果不深入研究它，我认为添加它并不难。对于 AVL 树，您总是需要知道每个节点的每个子树的深度(或者至少是平衡因子)。所以传播子树的大小应该不会太难。在旋转的情况下，您确切地知道每个节点和每个子树将落在何处，因此它应该只是对旋转的那些节点进行简单的重新计算。