template struct BIT { int n; vector w; BIT(int n, auto &in) : n(n), w(n + 1) { // 预处理填值 for (int i = 1; i <= n; i++) { add(i, in[i]); } } void add(int x, T v) { for (; x <= n; x += x & -x) { w[x] += v; } } T ask(int x) { // 前缀和查询 T ans = 0; for (; x; x -= x & -x) { ans += w[x]; } return ans; } T ask(int l, int r) { // 差分实现区间和查询 return ask(r) - ask(l - 1); } };