Binary Index Tree 树状数组

2026-05-052026-05-23

还缺个树上二分待填坑

template <typename T>
struct BIT {
  int n;
  vector<T> a;

  BIT(int _n) {
    init(_n);
  }

  void init(int _n) {
    n = _n;
    a.assign(n + 1, T{});
  }

  void update(int x, const T &v) {
    for (; x <= n; x += x & -x) {
      a[x] += v;
    }
  }

  T sum(int x) {
    T res = 0;
    for (; x; x -= x & -x) {
      res += a[x];
    }
    return res;
  }

  T query(int l, int r) {
    return sum(r) - sum(l - 1);
  }
};

习题

• ABC459 C