使用fenwick树的顺序统计树（BIT）-yiteyi-C++库

给定一个范围有限（0到1000000）的整数数组。我们需要使用fenwick树实现一个订单统计树。它应该支持四个操作：插入、删除、选择和排名。这里n表示Fenwick树的大小，q表示查询的数量。

null

每个查询都应该是以下4个操作之一。

insertElement（x）–将元素x插入到Fenwick树中，最坏情况时间复杂度为O（logn）
deleteElement（x）–从fenwick树中删除元素x，O（logn）的时间复杂度更差
FindkThminest（k）–查找存储在树中的第k个最小元素，其最坏情况时间复杂度为O（logn*logn）
Find（x）–查找元素x在树中的排名，即它在树的元素排序列表中的索引，时间复杂度为O（logn）

先决条件：二叉索引树或Fenwick树这个想法是创造一个最大限度的大小位。我们将一个元素作为索引插入位。当我们插入一个元素x时，我们将x的所有祖先的值增加1。要删除一个元素，我们将祖先的值减1。对于插入和删除，我们基本上都调用BIT的标准函数update（）。为了求秩，我们只需调用BIT的标准函数sum（）。为了找到第k个最小元素，我们进行二进制位搜索。

C++

                         // C++ program to find rank of an element                       
                         // and k-th smallest element.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         const                                     int                                     MAX_VAL = 1000001;                       
           
                         /* Updates element at index 'i' of BIT. */                       
                         void                                     update(                                     int                                     i,                                     int                                     add, vector<                                     int                                     >& BIT)                       
                         {                       
                                                 while                                     (i > 0 && i < BIT.size())                       
                                                 {                       
                                                 BIT[i] += add;                       
                                                 i = i + (i & (-i));                       
                                                 }                       
                         }                       
           
                         /* Returns cumulative sum of all elements of                       
                                                 fenwick tree/BIT from start upto and                       
                                                 including element at index 'i'. */                       
                         int                                     sum(                                     int                                     i, vector<                                     int                                     >& BIT)                       
                         {                       
                                                 int                                     ans = 0;                       
                                                 while                                     (i > 0)                       
                                                 {                       
                                                 ans += BIT[i];                       
                                                 i = i - (i & (-i));                       
                                                 }                       
           
                                                 return                                     ans;                       
                         }                       
           
                         // Returns lower bound for k in BIT.                       
                         int                                     findKthSmallest(                                     int                                     k, vector<                                     int                                     > &BIT)                       
                         {                       
                                                 // Do binary search in BIT[] for given                       
                                                 // value k.                       
                                                 int                                     l = 0;                       
                                                 int                                     h = BIT.size();                       
                                                 while                                     (l < h)                       
                                                 {                       
                                                 int                                     mid = (l + h) / 2;                       
                                                 if                                     (k <= sum(mid, BIT))                       
                                                 h = mid;                       
                                                 else                       
                                                 l = mid+1;                       
                                                 }                       
           
                                                 return                                     l;                       
                         }                       
           
                         // Insert x into BIT. We basically increment                       
                         // rank of all elements greater than x.                       
                         void                                     insertElement(                                     int                                     x, vector<                                     int                                     > &BIT)                       
                         {                       
                                                 update(x, 1, BIT);                       
                         }                       
           
                         // Delete x from BIT. We basically decreases                       
                         // rank of all elements greater than x.                       
                         void                                     deleteElement(                                     int                                     x, vector<                                     int                                     > &BIT)                       
                         {                       
                                                 update(x, -1, BIT);                       
                         }                       
           
                         // Returns rank of element. We basically                       
                         // return sum of elements from start to                       
                         // index x.                       
                         int                                     findRank(                                     int                                     x, vector<                                     int                                     > &BIT)                       
                         {                       
                                                 return                                     sum(x, BIT);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 vector<                                     int                                     > BIT(MAX_VAL);                       
                                                 insertElement(20, BIT);                       
                                                 insertElement(50, BIT);                       
                                                 insertElement(30, BIT);                       
                                                 insertElement(40, BIT);                       
           
                                                 cout <<                                     "2nd Smallest element is "                       
                                                 << findKthSmallest(2, BIT) << endl;                       
           
                                                 cout <<                                     "Rank of 40 is "                       
                                                 << findRank(40, BIT) << endl;                       
           
                                                 deleteElement(40, BIT);                       
           
                                                 cout <<                                     "Rank of 50 is "                       
                                                 << findRank(50, BIT) << endl;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find rank of an element                       
                         // and k-th smallest element.                       
                         import                                     java.util.Arrays;                       
           
                         class                                     GFG{                       
           
                         static                                     int                                     MAX_VAL =                                     1000001                                     ;                       
           
                         // Updates element at index 'i' of BIT                       
                         static                                     void                                     update(                                     int                                     i,                                     int                                     add,                       
                                                 Integer[] BIT)                       
                         {                       
                                                 while                                     (i >                                     0                                     && i < BIT.length)                       
                                                 {                       
                                                 BIT[i] += add;                       
                                                 i = i + (i & (-i));                       
                                                 }                       
                         }                       
           
                         // Returns cumulative sum of all elements                       
                         // of fenwick tree/BIT from start upto                       
                         // and including element at index 'i'.                       
                         static                                     int                                     sum(                                     int                                     i, Integer[] BIT)                       
                         {                       
                                                 int                                     ans =                                     0                                     ;                       
                                                 while                                     (i >                                     0                                     )                       
                                                 {                       
                                                 ans += BIT[i];                       
                                                 i = i - (i & (-i));                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         // Returns lower bound for k in BIT.                       
                         static                                     int                                     findKthSmallest(                                     int                                     k,                       
                                                 Integer[] BIT)                       
                         {                       
                                   
                                                 // Do binary search in BIT[]                       
                                                 // for given value k.                       
                                                 int                                     l =                                     0                                     ;                       
                                                 int                                     h = BIT.length;                       
                                   
                                                 while                                     (l < h)                       
                                                 {                       
                                                 int                                     mid = (l + h) /                                     2                                     ;                       
                                                 if                                     (k <= sum(mid, BIT))                       
                                                 h = mid;                       
                                                 else                       
                                                 l = mid +                                     1                                     ;                       
                                                 }                       
                                                 return                                     l;                       
                         }                       
           
                         // Insert x into BIT. We basically                       
                         // increment rank of all elements                       
                         // greater than x.                       
                         static                                     void                                     insertElement(                                     int                                     x, Integer[] BIT)                       
                         {                       
                                                 update(x,                                     1                                     , BIT);                       
                         }                       
           
                         // Delete x from BIT. We basically                       
                         // decreases rank of all elements                       
                         // greater than x.                       
                         static                                     void                                     deleteElement(                                     int                                     x, Integer[] BIT)                       
                         {                       
                                                 update(x, -                                     1                                     , BIT);                       
                         }                       
           
                         // Returns rank of element. We basically                       
                         // return sum of elements from start to                       
                         // index x.                       
                         static                                     int                                     findRank(                                     int                                     x, Integer[] BIT)                       
                         {                       
                                                 return                                     sum(x, BIT);                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 Integer[] BIT =                                     new                                     Integer[MAX_VAL];                       
                                                 Arrays.fill(BIT,                                     0                                     );                       
                                   
                                                 insertElement(                                     20                                     , BIT);                       
                                                 insertElement(                                     50                                     , BIT);                       
                                                 insertElement(                                     30                                     , BIT);                       
                                                 insertElement(                                     40                                     , BIT);                       
           
                                                 System.out.println(                                     "2nd Smallest element is "                                     +                       
                                                 findKthSmallest(                                     2                                     , BIT));                       
                                                 System.out.println(                                     "Rank of 40 is "                                     +                       
                                                 findRank(                                     40                                     , BIT));                       
           
                                                 deleteElement(                                     40                                     , BIT);                       
                                   
                                                 System.out.println(                                     "Rank of 50 is "                                     +                       
                                                 findRank(                                     50                                     , BIT));                       
                         }                       
                         }                       
           
                         // This code is contributed by sanjeev2552                       

输出：

2nd Smallest element is 30Rank of 40 is 3Rank of 50 is 3

如果你喜欢Geeksforgek，并且想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章