树状数组

lowbit操作

int lowbit(int x)
{
    return x & -x;
}

区间查询

$\quad O(logn)$

int getsum(int x) {  // a[1]..a[x]的和
  int res = 0;
  while (x > 0) {
    res = res + c[x];
    x = x - lowbit(x);
  }
  return res;
}

单点修改

$\quad O(logn)$

void add(int x, int k) { // a[x] = a[x] + k;
  while (x <= n) {  // 不能越界
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}

单点修改 + 区间查询

查询 a[l, r] 的和
此时c数组维护的是a数组的差分信息

void add(int x, int k)
{
    while(x <= n){
        c[x] = c[x] + k;
        x = x + lowbit(x);
    }
}
void range_add(int l, int r, int x)  // 区间[l, r] 加上 x
{
    add(l, x), add(r + 1, -x);
}
int getsum(int x)
{
    int res = 0;
    while(x > 0)
    {
        res += c[x];
        x = x - lowbit(x);
    }
    return res;
}

区间修改 + 单点查询

查询 a[l..r] 的和

void add(int x, int k)
{
    while(x <= n){
        c[x] = c[x] + k;
        x = x + lowbit(x);
    }
}
int getsum(int x)
{
    int res = 0;
    while(x > 0)
    {
        res += c[x];
        x = x - lowbit(x);
    }
    return res;
}
int query(int l, int r)
{
    return getsum(r) - getsum(l - 1);
}

区间修改 + 区间查询 (区间加区间和)

t1, t2 为差分数组

int t1[N], t2[N], n;
void add(int k, int v) {
  int v1 = k * v;
  while (k <= n) {
    t1[k] += v, t2[k] += v1; // 注意不能写成 t2[k] += k * v，因为 k 的值已经不是原数组的下标了
    k += lowbit(k);
  }
}
int getsum(int[] t, int k) {
  int res = 0;
  while (k) {
    res += t[k];
    k -= lowbit(k);
  }
  return res;
}

void range_add(int l, int r, int v) {
  add(l, v), add(r + 1, -v);  // 将区间加差分为两个前缀加
}
// 注意乘法过程中long long
long long get_range_sum(int l, int r) {
  return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) 
         - (getsum(t2, r) - getsum(t2, l - 1));
}

建树

$\quad O(nlogn)$
对于a数组，做n次单点修改操作

for( int i = 1; i <= n; i++ )
{
    add(i, a[i]);
}

$\quad O(n)$
每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献，即每次确定完儿子的值后，用自己的值更新自己的直接父亲。

void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) t[j] += t[i];
  }
}

$\quad O(n)$
$c[i]$表示的区间是 $[i - lowbit(i) + 1, i]$，那么我们可以先预处理一个$sum$前缀和数组，再计算$c$数组

void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] = sum[i] - sum[i - lowbit(i)];
  }
}

二维树状数组

单点加

void add(int x, int y, int v) {
    for (int i = x; i <= n ;i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            c[i][j] += v;
        }
    }
}

子矩阵和

int sum(int x, int y) {
  int res = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
      for (int j = y; j > 0; j -= lowbit(j)) {
          res += c[i][j];
      }
  }
  return res;
}
int ask(int x1, int y1, int x2, int y2) {
    return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
}

子矩阵加, 子矩阵和

typedef long long ll;
ll t1[N][N], t2[N][N], t3[N][N], t4[N][N];

void add(ll x, ll y, ll z) {
  for (int X = x; X <= n; X += lowbit(X))
    for (int Y = y; Y <= m; Y += lowbit(Y)) {
      t1[X][Y] += z;
      t2[X][Y] += z * x;  // 注意是 z * x 而不是 z * X，后面同理
      t3[X][Y] += z * y;
      t4[X][Y] += z * x * y;
    }
}
 //(xa, ya) 到 (xb, yb) 子矩阵
void range_add(ll xa, ll ya, ll xb, ll yb, ll z) { 
  add(xa, ya, z);
  add(xa, yb + 1, -z);
  add(xb + 1, ya, -z);
  add(xb + 1, yb + 1, z);
}

ll ask(ll x, ll y) {
  ll res = 0;
  for (int i = x; i; i -= lowbit(i))
    for (int j = y; j; j -= lowbit(j))
      res += (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j] -
             (x + 1) * t3[i][j] + t4[i][j];
  return res;
}

ll range_ask(ll xa, ll ya, ll xb, ll yb) {
  return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1);
}

维护区间最值

单点更新

$\quad O(log^{2}n)$

void update(int x, int v) {
  a[x] = v;
  for (int i = x; i <= n; i += lowbit(i)) {
    // 枚举受影响的区间
    c[i] = a[i];
    for (int j = 1; j < lowbit(i); j *= 2) {
      c[i] = max(c[i], c[i - j]);
    }
  }
}

维护区间最值

$\quad O(log^{2}n)$

// c数组维护的是区间最大值
int getmax(int l, int r) {
  int res = 0;
  while (r >= l) {
    res = max(res, a[r]);
    r--;
    for (r; r - lowbit(r) >= l; r -= lowbit(r)) {
      // 注意，循环条件不要写成 r - lowbit(r) + 1 >= l
      // 否则 l = 1 时，r 跳到 0 会死循环
      res = max(res, c[r]);
    }
  }
  return res;
}

指针版

class BIT {
private:
    vector<int> tree;
    int n;

public:
    BIT(int _n): n(_n), tree(_n + 1) {}

    static constexpr int lowbit(int x) {
        return x & (-x);
    }

    void update(int x, int d) {
        while (x <= n) {
            tree[x] += d;
            x += lowbit(x);
        }
    }

    int query(int x) const {
        int ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
};

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        long long sum = 0;
        vector<long long> preSum = {0};
        for (int v: nums) {
            sum += v;
            preSum.push_back(sum);
        }

        set<long long> allNumbers;
        for (long long x: preSum) {
            allNumbers.insert(x);
            allNumbers.insert(x - lower);
            allNumbers.insert(x - upper);
        }
        // 利用哈希表进行离散化
        unordered_map<long long, int> values;
        int idx = 0;
        for (long long x: allNumbers) {
            values[x] = idx;
            idx++;
        }

        int ret = 0;
        BIT bit(values.size());
        for (int i = 0; i < preSum.size(); i++) {
            int left = values[preSum[i] - upper], right = values[preSum[i] - lower];
            ret += bit.query(right + 1) - bit.query(left);
            bit.update(values[preSum[i]] + 1, 1);
        }
        return ret;
    }
};