树状数组

  1. template <typename T>
  2. struct Fenwick {
  3.   const int n;
  4.   vector<T> a;
  5.   Fenwick(int n): n(n), a(n + 1) {}
  6.   void add(int x, T v){
  7.     for(int i = x; i <= n; i += i & -i) a[i] += v;
  8.   }
  9.   T sum(int x) {
  10.     T rs = 0;
  11.     for(int i = x; i; i -= i & -i) {
  12.       rs += a[i];
  13.     }
  14.     return rs;
  15.   }
  16.   T rangeSum(int l, int r) {
  17.     if(l > r) return 0;
  18.     return sum(r) - sum(l - 1);
  19.   }
  20. };

二维树状数组

  1. template<class T>
  2. class Fenwick2D {
  3.     int n, m;
  4.     vector<vector<T>> c;
  5. public:
  6.     Fenwick2D() {}
  7.     Fenwick2D(int n, int m): n(n), m(m) {
  8.         c.resize(n + 1, vector<int>(m + 1, 0));
  9.     }
  10.     void add(int x, int y, T val) {
  11.         for(int i = x; i <= n; i += i & -i) {
  12.             for(int j = y; j <= m; j += j & -j) {
  13.                 c[i][j] += val;
  14.             }
  15.         }
  16.     }
  17.     int sum(int x, int y) {
  18.         T rs = 0;
  19.         for(int i = x; i; i -= i & -i) {
  20.             for(int j = y; j; j -= j & -j) {
  21.                 rs += c[i][j];
  22.             }
  23.         }
  24.         return rs;
  25.     }
  26.     int sum(int x0, int y0, int x, int y) {
  27.         return sum(x, y) - sum(x0 - 1, y) - sum(x, y0 - 1) + sum(x0 - 1, y0 - 1);
  28.     }
  29. };

例题

  1. https://leetcode-cn.com/problems/range-sum-query-2d-mutable/