树状数组总结——详解（单点/区间查询，单点/区间修改，逆序对）

2017-06-13 17:24
64人阅读
评论(0)
收藏
举报

版权声明：！！！本文为博主原创文章，若转载请附博主链接，一经发现盗版将追究责任。！！！

1、概述

　　树状数组(binary indexed tree)，是一种设计新颖的数组结构，它能够高效地获取数组中连续n个数的和。概括说，树状数组通常用于解决以下问题：数组{a}中的元素可能不断地被修改，怎样才能快速地获取连续几个数的和？

2、树状数组基本操作

　　传统数组(共n个元素)的元素修改和连续元素求和的复杂度分别为O(1)和O(n)。树状数组通过将线性结构转换成伪树状结构（线性结构只能逐个扫描元素，而树状结构可以实现跳跃式扫描），使得修改和求和复杂度均为O(lgn)，大大提高了整体效率。

给定序列（数列）A，我们设一个数组C满足

C[i] = A[i–2^k+ 1] + … + A[i]

其中，k为i在二进制下末尾0的个数，i从1开始算！

则我们称C为树状数组。

下面的问题是，给定i，如何求2^k?

答案很简单：2^k=i&(i^(i-1)) ，也就是i&(-i)

下面进行解释：

以i=6为例（注意：a_x表示数字a是x进制表示形式）：

(i)_10 = (0110)_2

(i-1)_10=(0101)_2

i xor (i-1) =(0011)_2

i and (i xor (i-1))  =(0010)_2

2^k = 2

C[6] = C[6-2+1]+…+A[6]=A[5]+A[6]

　数组C的具体含义如下图所示：

　　当我们修改A[i]的值时，可以从C[i]往根节点一路上溯，调整这条路上的所有C[]即可，这个操作的复杂度在最坏情况下就是树的高度即O(logn)。另外，对于求数列的前n项和，只需找到n以前的所有最大子树，把其根节点的C加起来即可。不难发现，这些子树的数目是n在二进制时1的个数，或者说是把n展开成2的幂方和时的项数,因此，求和操作的复杂度也是O(logn)。

　　树状数组能快速求任意区间的和：A[i] + A[i+1] + … + A[j]，设sum(k) = A[1]+A[2]+…+A[k]，则A[i] + A[i+1] + … + A[j] = sum(j)-sum(i-1)。

• 单点修改  &&  区间查询

         已知一个数列，你需要进行下面两种操作：

                   1.将某一个数加上x

                   2.求出某区间每一个数的和

[cpp]
view plain
copy
print
?

1. /************************************************************************* 
2.      > Author: wzw-cnyali 
3.      > Created Time: 2017/6/13 10:33:11 
4.  ************************************************************************/  
5.   
6. #prag\  
7. ma GCC optimize(&＃8220;O3&＃8221;)  
8.   
9. #include  
10. #include  
11. #include  
12. #include  
13. #include  
14. #include  
15.   
16. using namespace std;  
17.   
18. typedef long long LL;  
19.   
20. typedef unsigned long long uLL;  
21.   
22. #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)  
23. #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; &＃8212; i)  
24. #define EREP(i, a) for(register int i = (be[a]); i != -1; i = nxt[i])  
25. #define debug(&＃8230;) fprintf(stderr, __VA_ARGS__)  
26. #define mem(a, b) memset((a), b, sizeof(a))  
27.   
28. template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }  
29. template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }  
30.   
31. char buff[1 << 25], *buf = buff;  
32.   
33. template <class T>  
34. T read(T sum = 0, T fg = 0)  
35. {  
36.     while(*buf < &＃8216;0&＃8217; || *buf > &＃8216;9&＃8217;) { fg |= *buf == &＃8216;-&＃8216;; buf++; }  
37.     while(*buf >= &＃8216;0&＃8217; && *buf <= &＃8216;9&＃8217;) { sum = sum * 10 + *buf &＃8211; &＃8216;0&＃8217;; buf++; }  
38.     return fg ? -sum : sum;  
39. }  
40.   
41. const int inf = 1e9;  
42.   
43. const LL INF = 1e17;  
44.   
45. const int Size = 500010;  
46.   
47. const int maxn = 100000;  
48.   
49. const int maxm = 100000;  
50.   
51. int n, m;  
52. int a[Size];  
53.   
54. struct index_tree  
55. {  
56. #define lowbit(x) ((x) & (-x))  
57.     void add(int x, int val)  
58.     {  
59.         for(; x <= n; x += lowbit(x)) a[x] += val;  
60.     }  
61.     int query(int x)  
62.     {  
63.         int ans = 0;  
64.         for(; x; x -= lowbit(x)) ans += a[x];  
65.         return ans;  
66.     }  
67. }tree;  
68.   
69. int main()  
70. {  
71. #ifndef ONLINE_JUDGE  
72.     freopen(&＃8220;input.in&＃8221;, &＃8220;r&＃8221;, stdin);  
73.     freopen(&＃8220;output.out&＃8221;, &＃8220;w&＃8221;, stdout);  
74. #endif  
75.     fread(buff, 1, 1 << 25, stdin);  
76.     n = read<int>(), m = read<int>();  
77.     REP(i, 1, n) tree.add(i, read<int>());  
78.     while(m&＃8211;)  
79.     {  
80.         int tp = read<int>();  
81.         if(tp == 1)  
82.         {  
83.             int x = read<int>(), val = read<int>();  
84.             tree.add(x, val);  
85.         }  
86.         else  
87.         {  
88.             int x = read<int>(), y = read<int>();  
89.             printf(&＃8220;%d\n&＃8221;, tree.query(y) &＃8211; tree.query(x &＃8211; 1));  
90.         }  
91.     }  
92.     return 0;  
93. }  

题目链接：
https://www.luogu.org/problem/show?pid=3374

• 区间修改  &&  单点查询

                已知一个数列，你需要进行下面两种操作：

                        1.将某区间每一个数数加上x

                        2.求出某一个数的值

               思路：

        这里要引入差分数组这种东西，我们记d[i] = a[i] &＃8211; a[i-1]（a为原数组），这样我们记sigma（d[i]） = a[i] ，为什么呢，观察式子sigma(d[i]) = a[1] + a[2] &＃8211; a[1] +ａ［３］．．．这样一直下去就得到了我们的原数组。
有什么用呢？如果我们往一段区间上加ｋ，在差分数组上如何体现呢？我们举个例子：
                       ａ：１,２,３,４,５
                       ｄ：１,１,１,１,１
                       ２～４加１
        如果我们盲目的在２到４上加１，就会发现会影响后面的数（因为是前缀和），所以我们在２这个位置加一，用树状数组更新，在５的位置减一用树状数组更新就ｏｋ了
                       ａ：１，３，４，５，５
                       ｄ：１，２，１，１，０

[cpp]
view plain
copy
print
?

1. /************************************************************************* 
2.      > Author: wzw-cnyali 
3.      > Created Time: 2017/6/13 11:11:16 
4.  ************************************************************************/  
5.   
6. #include  
7. #include  
8. #include  
9. #include  
10. #include  
11. #include  
12.   
13. #prag\  
14. ma GCC optimize(&＃8220;O3&＃8221;)  
15.   
16. using namespace std;  
17.   
18. typedef long long LL;  
19.   
20. typedef unsigned long long uLL;  
21.   
22. #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)  
23. #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; &＃8212; i)  
24. #define EREP(i, a) for(register int i = (be[a]); i != -1; i = nxt[i])  
25. #define debug(&＃8230;) fprintf(stderr, __VA_ARGS__)  
26. #define mem(a, b) memset((a), b, sizeof(a))  
27.   
28. template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }  
29. template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }  
30.   
31. char buff[1 << 25], *buf = buff;  
32.   
33. template <class T>  
34. T Fread(T sum = 0, T fg = 0)  
35. {  
36.     while(*buf < &＃8216;0&＃8217; || *buf > &＃8216;9&＃8217;) { fg |= *buf == &＃8216;-&＃8216;; buf++; }  
37.     while(*buf >= &＃8216;0&＃8217; && *buf <= &＃8216;9&＃8217;) { sum = sum * 10 + *buf &＃8211; &＃8216;0&＃8217;; buf++; }  
38.     return fg ? -sum : sum;  
39. }  
40.   
41. template <class T>  
42. T read(T sum = 0, T fg = 0)  
43. {  
44.     char c = getchar();  
45.     while(c < &＃8216;0&＃8217; || c > &＃8216;9&＃8217;) { fg |= c == &＃8216;-&＃8216;; c = getchar(); }  
46.     while(c >= &＃8216;0&＃8217; && c <= &＃8216;9&＃8217;) { sum = sum * 10 + c &＃8211; &＃8216;0&＃8217;; c = getchar(); }  
47.     return fg ? -sum : sum;  
48. }  
49.   
50. const int inf = 1e9;  
51.   
52. const LL INF = 1e17;  
53.   
54. const int Size = 500010;  
55.   
56. const int maxn = 100000;  
57.   
58. const int maxm = 100000;  
59.   
60. int n, m;  
61. int a[Size];  
62.   
63. struct index_tree   
64. {  
65. #define lowbit(x) ((x) & (-x))  
66.     int tree[Size];  
67.   
68.     void add(int x, int val)  
69.     {  
70.         for(; x <= n; x += lowbit(x)) tree[x] += val;  
71.     }  
72.   
73.     int query(int x)  
74.     {  
75.         int ans = 0;  
76.         for(; x; x -= lowbit(x)) ans += tree[x];  
77.         return ans;  
78.     }  
79. }tree;  
80.   
81. int main()  
82. {  
83. #ifndef ONLINE_JUDGE  
84.     freopen(&＃8220;input.in&＃8221;, &＃8220;r&＃8221;, stdin);  
85.     freopen(&＃8220;output.out&＃8221;, &＃8220;w&＃8221;, stdout);  
86. #endif  
87.     fread(buff, 1, 1 << 25, stdin);  
88.     n = Fread<int>(), m = Fread<int>();  
89.     REP(i, 1, n)  
90.     {  
91.         a[i] = Fread<int>();  
92.         tree.add(i, a[i] &＃8211; a[i &＃8211; 1]);  
93.     }  
94.     while(m&＃8211;)  
95.     {  
96.         if(Fread<int>() == 1)  
97.         {  
98.             int x = Fread<int>(), y = Fread<int>(), val = Fread<int>();  
99.             tree.add(x, val);  
100.             tree.add(y + 1, -val);  
101.         }  
102.         else printf(&＃8220;%d\n&＃8221;, tree.query(Fread<int>()));  
103.     }  
104.     return 0;  
105. }  

题目链接：https://www.luogu.org/problem/show?pid=3368

• 区间修改  &&  区间查询

               已知一个数列，你需要进行下面两种操作：

                        1.将某区间每一个数加上x

                        2.求出某区间每一个数的和

  首先观察式子：

a[1]+a[2]+&＃8230;+a[n]

= (c[1]) + (c[1]+c[2]) + &＃8230; + (c[1]+c[2]+&＃8230;+c[n]) 

= n*c[1] + (n-1)*c[2] +&＃8230; +c[n]

= n * (c[1]+c[2]+&＃8230;+c[n]) &＃8211; (0*c[1]+1*c[2]+&＃8230;+(n-1)*c[n])    (式子①)

那么我们就维护一个数组c2[n]，其中c2[i] = (i-1)*c[i]

每当修改c的时候，就同步修改一下c2，这样复杂度就不会改变

那么式子①=n*sigma(c,n) &＃8211; sigma(c2,n)

于是我们做到了在O(logN)的时间内完成一次区间和查询

一件很好的事情就是树状数组的常数比其他NlogN的数据结构小得多，实际上它的计算次数比NlogN要小很多，再加上它代码短，是OI中的利器

[cpp]
view plain
copy
print
?

1. /************************************************************************* 
2.      > Author: wzw-cnyali 
3.      > Created Time: 2017/6/13 15:18:18 
4.  ************************************************************************/  
5.   
6. #include  
7. #include  
8. #include  
9. #include  
10. #include  
11. #include  
12.   
13. #prag\  
14. ma GCC optimize(&＃8220;O3&＃8221;)  
15.   
16. using namespace std;  
17.   
18. typedef long long LL;  
19.   
20. typedef unsigned long long uLL;  
21.   
22. #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)  
23. #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; &＃8212; i)  
24. #define EREP(i, a) for(register int i = (be[a]); i != -1; i = nxt[i])  
25. #define debug(&＃8230;) fprintf(stderr, __VA_ARGS__)  
26. #define mem(a, b) memset((a), b, sizeof(a))  
27.   
28. template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }  
29. template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }  
30.   
31. char buff[1 << 21], *buf = buff;  
32.   
33. template <class T>  
34. T Fread(T sum = 0, T fg = 0)  
35. {  
36.     while(*buf < &＃8216;0&＃8217; || *buf > &＃8216;9&＃8217;) { fg |= *buf == &＃8216;-&＃8216;; buf++; }  
37.     while(*buf >= &＃8216;0&＃8217; && *buf <= &＃8216;9&＃8217;) { sum = sum * 10 + *buf &＃8211; &＃8216;0&＃8217;; buf++; }  
38.     return fg ? -sum : sum;  
39. }  
40.   
41. template <class T>  
42. T read(T sum = 0, T fg = 0)  
43. {  
44.     char c = getchar();  
45.     while(c < &＃8216;0&＃8217; || c > &＃8216;9&＃8217;) { fg |= c == &＃8216;-&＃8216;; c = getchar(); }  
46.     while(c >= &＃8216;0&＃8217; && c <= &＃8216;9&＃8217;) { sum = sum * 10 + c &＃8211; &＃8216;0&＃8217;; c = getchar(); }  
47.     return fg ? -sum : sum;  
48. }  
49.   
50. const int inf = 1e9;  
51.   
52. const LL INF = 1e17;  
53.   
54. const int Size = 100010;  
55.   
56. const int maxn = 100000;  
57.   
58. const int maxm = 100000;  
59.   
60. int n, m;  
61.   
62. struct index_tree   
63. {  
64. #define lowbit(x) ((x) & (-x))  
65.   
66.     void add(LL *array, int x, LL val)  
67.     {  
68.         for(; x <= n; x += lowbit(x)) array[x] += val;  
69.     }  
70.   
71.     LL query(LL *array, int x)  
72.     {  
73.         LL ans = 0;  
74.         for(; x; x -= lowbit(x)) ans += array[x];  
75.         return ans;  
76.     }  
77. }tree;  
78.   
79. LL c1[Size], c2[Size];  
80.   
81. int main()  
82. {  
83. #ifndef ONLINE_JUDGE  
84.     freopen(&＃8220;input.in&＃8221;, &＃8220;r&＃8221;, stdin);  
85.     freopen(&＃8220;output.out&＃8221;, &＃8220;w&＃8221;, stdout);  
86. #endif  
87.     fread(buff, 1, 1 << 21, stdin);  
88.     n = Fread<int>(), m = Fread<int>();  
89.     LL last_x = 0;  
90.     REP(i, 1, n)  
91.     {  
92.         LL x = Fread();  
93.         tree.add(c1, i, x &＃8211; last_x);  
94.         tree.add(c2, i, (x &＃8211; last_x) * (i &＃8211; 1));  
95.         last_x = x;  
96.     }  
97.     while(m&＃8211;)  
98.     {  
99.         if(Fread<int>() == 1)  
100.         {  
101.             int x = Fread<int>(), y = Fread<int>();  
102.             LL val = Fread();  
103.             tree.add(c1, x, val); tree.add(c1, y + 1, -val);  
104.             tree.add(c2, x, val * (x &＃8211; 1)); tree.add(c2, y + 1, -val * y);  
105.         }  
106.         else  
107.         {  
108.             int x = Fread<int>(), y = Fread<int>();  
109.             LL sum1 = (x &＃8211; 1) * tree.query(c1, x &＃8211; 1) &＃8211; tree.query(c2, x &＃8211; 1);  
110.             LL sum2 = y * tree.query(c1, y) &＃8211; tree.query(c2, y);  
111.             printf(&＃8220;%lld\n&＃8221;, sum2 &＃8211; sum1);  
112.         }  
113.     }  
114.     return 0;  
115. }  

题目链接：https://www.luogu.org/problem/show?pid=3372

• 逆序对

             对于一个包含n个非负整数的数组a，如果有ia[j]，则称（a[i]，A[j]）为数组a中的一个逆序对。

           即逆序数就是前面比后面大的一对数。

[cpp]
view plain
copy
print
?

1. /************************************************************************* 
2.      > Author: wzw-cnyali 
3.      > Created Time: 2017/6/13 16:59:03 
4.  ************************************************************************/  
5.   
6. #include  
7. #include  
8. #include  
9. #include  
10. #include  
11. #include  
12.   
13. #prag\  
14. ma GCC optimize(&＃8220;O3&＃8221;)  
15.   
16. using namespace std;  
17.   
18. typedef long long LL;  
19.   
20. typedef unsigned long long uLL;  
21.   
22. #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)  
23. #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; &＃8212; i)  
24. #define EREP(i, a) for(register int i = (be[a]); i != -1; i = nxt[i])  
25. #define debug(&＃8230;) fprintf(stderr, __VA_ARGS__)  
26. #define mem(a, b) memset((a), b, sizeof(a))  
27.   
28. template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }  
29. template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }  
30.   
31. char buff[1 << 25], *buf = buff;  
32.   
33. template <class T>  
34. T Fread(T sum = 0, T fg = 0)  
35. {  
36.     while(*buf < &＃8216;0&＃8217; || *buf > &＃8216;9&＃8217;) { fg |= *buf == &＃8216;-&＃8216;; buf++; }  
37.     while(*buf >= &＃8216;0&＃8217; && *buf <= &＃8216;9&＃8217;) { sum = sum * 10 + *buf &＃8211; &＃8216;0&＃8217;; buf++; }  
38.     return fg ? -sum : sum;  
39. }  
40.   
41. template <class T>  
42. T read(T sum = 0, T fg = 0)  
43. {  
44.     char c = getchar();  
45.     while(c < &＃8216;0&＃8217; || c > &＃8216;9&＃8217;) { fg |= c == &＃8216;-&＃8216;; c = getchar(); }  
46.     while(c >= &＃8216;0&＃8217; && c <= &＃8216;9&＃8217;) { sum = sum * 10 + c &＃8211; &＃8216;0&＃8217;; c = getchar(); }  
47.     return fg ? -sum : sum;  
48. }  
49.   
50. const int inf = 1e9;  
51.   
52. const LL INF = 1e17;  
53.   
54. const int Size = 100000;  
55.   
56. const int maxn = 100000;  
57.   
58. const int maxm = 100000;  
59.   
60. int n;  
61.   
62. struct node  
63. {  
64.     int val, id;  
65. }a[Size];  
66.   
67. bool cmp(node a, node b)  
68. {  
69.     return a.val < b.val;  
70. }  
71.   
72. struct index_tree  
73. {  
74. #define lowbit(x) ((x) & (-x))  
75.     int tree[Size];  
76.     void add(int x)  
77.     {  
78.         for(; x <= n; x += lowbit(x)) tree[x]++;  
79.     }  
80.   
81.     int query(int x)  
82.     {  
83.         int ans = 0;  
84.         for(; x; x -= lowbit(x)) ans += tree[x];  
85.         return ans;  
86.     }  
87. }tree;  
88.   
89. int c[Size];  
90.   
91. int main()  
92. {  
93. #ifndef ONLINE_JUDGE  
94.     freopen(&＃8220;input.in&＃8221;, &＃8220;r&＃8221;, stdin);  
95.     freopen(&＃8220;output.out&＃8221;, &＃8220;w&＃8221;, stdout);  
96. #endif  
97.     fread(buff, 1, 1 << 25, stdin);  
98.     n = Fread<int>();  
99.     REP(i, 1, n) a[i] = (node){Fread<int>(), i};  
100.     sort(a + 1, a + n + 1, cmp);  
101.   
102.     REP(i, 1, n) c[a[i].id] = i;  
103.   
104.     int ans = 0;  
105.     DREP(i, n, 1)  
106.     {  
107.         ans += tree.query(c[i]);  
108.         tree.add(c[i]);  
109.     }  
110.     printf(&＃8220;%d\n&＃8221;, ans);  
111.     return 0;  
112. }