树状数组

单点加，区间和。

需要运算满足结合律且可差分，如加法（和）、乘法（积）、异或等。

• 结合律： $(x\circ y)\circ z=x\circ (y\circ z)$ ，其中 $\circ$ 是一个二元运算符。
• 可差分：具有逆运算的运算，即已知 $x\circ y$ 和 $x$ 可以求出 $y$ 。

struct Fenwick {
  int n;
  vector<int> a;
  Fenwick(int _n): n(_n), a(_n + 10) {}
  Fenwick(const vector<int> &arr) {
    n = arr.size();
    a = vector<int>(n + 10);
    // O(n) 建树
    for (int i = 1; i <= n; ++i) {
      a[i] += arr[i - 1];
      int j = i + lowbit(i);
      if (j <= n) {
        a[j] += a[i];
      }
    }
  }
  static int lowbit(int x) {
    return x & -x;
  }
  // 单点加
  void add(int k, int x) {
    while (k <= n) {
      a[k] += x;
      k += lowbit(k);
    }
  }
  // 查询前缀和
  int query(int k) {
    int res = 0;
    while (k > 0) {
      res += a[k];
      k -= lowbit(k);
    }
    return res;
  }
  // 区间查询
  int query(int l, int r) {
    return query(r) - query(l - 1);
  }
};

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (auto &x : a) {
    cin >> x;
  }
  Fenwick tree(a);
  while (m--) {
    int q;
    cin >> q;
    if (q == 1) {
      int pos, x;
      cin >> pos >> x;
      tree.add(pos, x);
    } else if (q == 2) {
      int l, r;
      cin >> l >> r;
      cout << tree.query(l, r) << endl;
    }
  }
}

区间加，单点查询。

维护差分数组即可。

区间加，区间和。

struct Tree {
private:
  vector<int> t1, t2;
  int n;

  void add_(int k, int x) {
    int v1 = k * x;
    while (k <= n) {
      t1[k] += x, t2[k] += v1;
      k += lowbit(k);
    }
  }

  int query_(vector<int> &t, int k) {
    int res = 0;
    while (k) {
      res += t[k];
      k -= lowbit(k);
    }
    return res;
  }

public:
  Tree(int _n): t1(_n + 2), t2(_n + 2), n(_n) {}

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

  // 区间加
  void add(int l, int r, int v) {
    add_(l, v);
    add_(r + 1, -v);
  }

  // 求区间和
  int query(int l, int r) {
    return (r + 1) * query_(t1, r) - l * query_(t1, l - 1)
           - (query_(t2, r) - query_(t2, l - 1));
  }
};

void solve() {
  int n, m;
  cin >> n >> m;
  Tree tr(n);
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    tr.add(i, i, x);
  }
  while (m--) {
    int q;
    cin >> q;
    if (q == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      tr.add(l, r, x);
    } else if (q == 2) {
      int l, r;
      cin >> l >> r;
      cout << tr.query(l, r) << endl;
    }
  }
}

二维，子矩阵加，单点查询

改一改就是单点修改，子矩阵查询了。

LOJ-133

struct Tree {
  int n, m;
  vector<vector<int>> t;

  Tree(int _n, int _m): n(_n), m(_m), t(_n + 2, vector<int>(_m + 2, 0)) {}

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

  // 单点加
  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)) {
        t[i][j] += v;
      }
    }
  }

  // 查询前缀和
  int query(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 += t[i][j];
      }
    }
    return res;
  }
};

void solve() {
  int n, m;
  cin >> n >> m;
  Tree tree(n, m);

  // 区间加，维护差分数组时使用
  auto addRange = [&](int x1, int y1, int x2, int y2, int v) {
    tree.add(x1, y1, v);
    tree.add(x1, y2 + 1, -v);
    tree.add(x2 + 1, y2 + 1, v);
    tree.add(x2 + 1, y1, -v);
  };

  // 区间查询，维护原数组时使用
  auto queryRange = [&](int x1, int y1, int x2, int y2) {
    return tree.query(x2, y2) - tree.query(x2, y1 - 1) - tree.query(x1 - 1, y2)
           + tree.query(x1 - 1, y1 - 1);
  };

  int op;

  while (cin >> op) {
    if (op == 1) {
      int x, y, k;
      cin >> x >> y >> k;
      tree.add(x, y, k);
    } else if (op == 2) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      cout << queryRange(x1, y1, x2, y2) << endl;
    }
  }
}

二维，子矩阵加，子矩阵查询

LOJ-135

struct Tree {
private:
  vector<vector<int>> t1, t2, t3, t4;
  int n, m;

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

  // 单点加
  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)) {
        t1[i][j] += v;
        t2[i][j] += v * x;
        t3[i][j] += v * y;
        t4[i][j] += v * x * y;
      }
    }
  }

  // 查询前缀和
  int query(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 += (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j]
               - (x + 1) * t3[i][j] + t4[i][j];
      }
    }
    return res;
  }

public:
  Tree(int _n, int _m): n(_n), m(_m) {
    t1 = t2 = t3 = t4 = vector<vector<int>>(_n + 2, vector<int>(_m + 2));
  }

  // 子矩阵加
  void addRange(int x1, int y1, int x2, int y2, int v) {
    add(x1, y1, v);
    add(x1, y2 + 1, -v);
    add(x2 + 1, y1, -v);
    add(x2 + 1, y2 + 1, v);
  }

  // 子矩阵查询
  int queryRange(int x1, int y1, int x2, int y2) {
    return query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2)
           + query(x1 - 1, y1 - 1);
  }
};

void solve() {
  int n, m;
  cin >> n >> m;
  Tree tree(n, m);

  int op;
  while (cin >> op) {

    if (op == 1) {
      int x1, y1, x2, y2, k;
      cin >> x1 >> y1 >> x2 >> y2 >> k;
      tree.addRange(x1, y1, x2, y2, k);
    } else if (op == 2) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      cout << tree.queryRange(x1, y1, x2, y2) << endl;
    }
  }
}

权值树状数组

TODO 完善代码

维护 $b_x$ 为 $x$ 在 $a$ 中出现的次数，对 $b$ 建树状数组。

单点修改，求 kth：

// 权值树状数组查询第 k 小
int kth(int k) {
  int sum = 0, x = 0;
  for (int i = log2(n); ~i; --i) {
    x += 1 << i;                   // 尝试扩展
    if (x >= n || sum + t[x] >= k) // 如果扩展失败
      x -= 1 << i;
    else
      sum += t[x];
  }
  return x + 1;
}