树状数组

概念：树状数组（Fenwick Tree）以二进制低位 lowbit 划分区间，紧凑地维护前缀聚合值。最常用模型是单点修改、前缀和查询。

关键步骤

更新 i 时不断加上 i&-i；查询前缀时不断减去它。区间和由 sum(r)-sum(l-1) 得到，索引必须从 1 开始。

int n; vector<long long> bit;
void add(int i,long long v){ for(;i<=n;i+=i&-i) bit[i]+=v; }
long long sum(int i){
    long long r=0; for(;i>0;i-=i&-i) r+=bit[i]; return r;
}
long long rangeSum(int l,int r){ return sum(r)-sum(l-1); }

复杂度

单点更新和前缀/区间查询均为 O(log n)，空间 O(n)。它要求操作可用前缀差还原区间，求区间最值通常应使用线段树。