一维树状数组

有手就行。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1000010;
  4. int n, a[N];
  5. inline int lowbit(int x) { return x & (-x); }
  6. int ask(int x) {
  7.     int res = 0;
  8.     for (; x; x -= lowbit(x)) res += a[x];
  9.     return res;
  10. }
  11. void add(int x, int val) {
  12.     for (; x <= n; x += lowbit(x)) a[x] += val;
  13. }
  14. int query(int l, int r) {
  15.     return ask(r) - ask(l - 1);
  16. }

二维树状数组

下面这个代码是用来处理差分数据的，其实单纯处理二维求和和单点修改更简单些。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1010;
  4. int n, m;
  5. int a[N][N];//原数组
  6. int d[N][N];//差分数组
  7. inline int lowbit(int x) { return x & (-x); }
  8. //对差分数组某处加上值
  9. void add(int x, int y, int val) {
  10.     for (; x <= n; x += lowbit(x))
  11.         for (; y <= m; y += lowbit(y))
  12.             d[x][y] += val;
  13. }
  14. //对矩阵a (x1,y1)到(x2,y2)集体加上v
  15. void real_add(int x1, int y1, int x2, int y2, int val) {
  16.     add( x1 ,  y1 ,  val);
  17.     add( x1 , y2+1, -val);
  18.     add(x2+1,  y1 , -val);
  19.     add(x2+1, y2+1,  val);
  20. }
  21. //查询a[i][j]的值
  22. int query(int x, int y) {
  23.     int ans = 0;
  24.     for (; x; x -= lowbit(x))
  25.         for (; y; y -= lowbit(y))
  26.             ans += d[x][y];
  27.     return ans;
  28. }

ST表

取对数不要用数学库的对数函数，那玩意复杂度不是常数，还是预处理比较好。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 100010;
  4. int n;
  5. //初始数据
  6. int a[N];
  7. //ST表
  8. int ST[N][25], lg[N];
  9. void init()
  10. {
  11.     //log预处理
  12.     lg[1] = 0;
  13.     for (int i = 2; i <= n; i++)
  14.         lg[i] = lg[i / 2] + 1;
  15.     //ST表预处理
  16.     for (int i = 1; i <= n; ++i)
  17.         ST[i][0] = a[i];
  18.     for (int k = 1; k <= 20; ++k)
  19.         for (int i = 1; i + (1 << k) - 1 <= n; ++i)
  20.             ST[i][k] = max(ST[i][k - 1], ST[i + (1 << (k - 1))][k - 1]);
  21. }
  22. //询问
  23. inline int query(int l, int r) {
  24.     int k = lg[r - l + 1];
  25.     return max(ST[l][k], ST[r - (1 << k) + 1][k]);
  26. }