维护数字的数据结构
请建议一种数据结构来维护数字，以便我可以回答以下查询 -
Find(int n) - O(log(n))
计算小于 k = O(log(n)) 的数字数量
插入 - O(Log(n))
这不是作业，而是我在解决更大问题时遇到的一个较小问题 - 成绩较好但jee排名较低的学生人数
我虽然有一个 avl 树，它在每个节点处维护子树中的节点数量。但我不知道在完成插入和重新平衡时如何在每个节点上维护此计数。
Please suggest a data structure to maintain numbers in such a way that i can answer the following queries -
Find(int n) - O(log(n))
Count number of numbers less than k = O(log(n))
Insert - O(Log(n))
It's not homework, but a smaller problem that i am encountering to solve a bigger one - Number of students with better grades and lower jee rank
I have though of an avl tree with maintaining number of nodes in subtree at each nod.But i dont know how to maintain this count at each node when an insert is being done and re-balancing is being done.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我也会尝试使用 AVL 树。如果不深入研究，我认为添加这一点并不难。对于 AVL 树，您始终需要知道每个节点的每个子树的深度（或至少是平衡因子）。因此传播子树的大小应该不会太难。在旋转的情况下，您确切地知道每个节点和每个子树将落在哪里，因此它应该只是对那些旋转的节点进行简单的重新计算。
I would also try using an AVL Tree. Without looking much deeper into it, I don't think this would be too hard to add. In case of an AVL tree you alway need to know the depth of each subtree for each node anyway (or at least the balancing factor). So it should not be too hard to propagate the size of the subtrees. In case of an rotation, you know exactely where each node and each subtree will land, so it should be just a simple recalculation for those nodes, which are rotated.
在二叉树中查找是 O(log(n))，插入也是如此。
如果将子树大小存储在节点中：
所以子树大小就像查找一样，O(log(n))。
Finding in a binary tree is O(log(n)), inserting too.
If you store the subtree size in the node:
So subtree size is like a find, O(log(n)).
查看堆数据结构的不同变体，例如此处。
Have a look at the different variants of heap data structures, e.g. here.