树状数组（Binary Indexed Tree, BIT）
- 本质上是按照二分对数组进行分组，维护和查询都是O(lgn)的复杂度
- 树状数组与线段树：树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树解决，而线段树能解决的树状数组不一定能解决。相比较而言，树状数组效率要高很多。
- lowbit
- lowbit = x & (-x)
- lowbit(x)也可以理解为能整除x的最大的2的幂次
- c[i]存放的是在i号之前（包括i号）lowbit(i)个整数的和（即：c[i]的覆盖长度是lowbit(i) ）
- 树状数组的下标必须从1开始
单点更新，区间查询
int getsum(int x)函数：返回前x个整数之和
|
1 2 3 4 5 6 |
int getsum(int x) { int sum = 0; for(int i = x; i >= 1; i -= lowbit(x)) sum += c[i]; return sum; } |
- 如果要求[x, y]之内的数的和，可以转换成getsum(y) – getsum(x – 1)来解决
void update(x, v)函数：将第x个数加上一个数v
|
1 2 3 4 |
void update(int x, int v) { for(int i = x; i <= n; i += lowbit(x)) c[i] += v; } |
经典应用：统计序列中在元素左边比该元素小的元素个数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <cstdio> #include <cstring> const int maxn = 10010; #define lowbit(i) ((i) & (-i)) int c[maxn]; void update(int x, int v) { for(int i = x; i < maxn; i += lowbit(i)) c[i] += v; } int getsum(int x) { int sum = 0; for(int i = x; i >= 1; i -= lowbit(i)) sum += c[i]; return sum; } int main() { int n, x; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &x); update(x, 1); printf("%d\n", getsum(x - 1)); } return 0; } |
如果是求序列第k大的问题：
可以用二分法查询第一个满足getsum(i) >= k的i
|
1 2 3 4 5 6 7 8 9 10 11 |
int findKthElement(int k) { int l = 1, r = maxn; mid; while(l < r) { mid = (l + r) / 2; if(getsum(mid) >= K) r = mid; else l = mid + 1; } return l; } |
如果给定一个二维整数矩阵A，求A[1][1]~A[x][y]这个子矩阵中所有元素之和，以及给单点A[x][y]加上整数v：
只需把getsum和update函数中的for循环改为两重
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int c[maxn][maxn]; void update(int x, int y, int v) { for(int i = x; i < maxn; i += lowbit(i)) { for(int j = y; j < maxn; j += lowbit(j)) { c[i][j] += v; } } } int getsum(int x, int y) { int sum = 0; for(int i = x; i >= 1; i -= lowbit(i)) { for(int j = y; j >= 1; j -= lowbit(j)) sum += c[i][j]; } return sum; } |
区间更新，单点查询
- 将getsum改为沿着i增大lowbit(i)的方向
- 将update改为沿着i减小的lowbit(i)的方向
- c[i]不再表示这段区间的元素之和，而是表示这段区间每个数被加了多少
- int getsum(int x)返回第x个整数的值（就是从小块到大块累加一共被增加了多少）
|
1 2 3 4 5 6 |
int getsum(int x) { int sum = 0; for(int i = x; i < maxn; i += lowbit(i)) sum += c[i]; return sum; } |
- void update(int x, int v)是将前x个整数都加上v
|
1 2 3 4 |
void update(int x, int v) { for(int i = x; i >= 0; i -= lowbit(i)) c[i] += v; } |
- 所以，~~i从x往后是从小块更新到大块c[i]，i从x往前是累加前面的覆盖块的值~
1057. Stack (30)-PAT甲级真题（树状数组）
- 求栈内所有元素的中位数：用排序查询的方法会超时~~~用树状数组，即求第k = (s.size() + 1) / 2大的数。查询小于等于x的数的个数是否等于k的时候用二分法更快~
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <cstdio> #include <stack> #define lowbit(i) ((i) & (-i)) const int maxn = 100010; using namespace std; int c[maxn]; stack<int> s; void update(int x, int v) { for(int i = x; i < maxn; i += lowbit(i)) c[i] += v; } int getsum(int x) { int sum = 0; for(int i = x; i >= 1; i -= lowbit(i)) sum += c[i]; return sum; } void PeekMedian() { int left = 1, right = maxn, mid, k = (s.size() + 1) / 2; while(left < right) { mid = (left + right) / 2; if(getsum(mid) >= k) right = mid; else left = mid + 1; } printf("%d\n", left); } int main() { int n, temp; scanf("%d", &n); char str[15]; for(int i = 0; i < n; i++) { scanf("%s", str); if(str[1] == 'u') { scanf("%d", &temp); s.push(temp); update(temp, 1); } else if(str[1] == 'o') { if(!s.empty()) { update(s.top(), -1); printf("%d\n", s.top()); s.pop(); } else { printf("Invalid\n"); } } else { if(!s.empty()) PeekMedian(); else printf("Invalid\n"); } } return 0; } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
