树状数组

· · 算法·理论

树状数组

明确

树状数组仅能实现两个功能：

  1. 单点修改
  2. 区间查询

表示


如图，以 4 为例，二进制是100，它是010（2）和011（3）的父亲，是1000（8）的儿子
那么，对于c,它的父亲是二进制下，最后一个 1 (lowbit(c)) + 1

区间查询

令c[i]等于它管辖的数的和
以7为例，即111 求区间[1,7]就等于c[111] +c[110]+c[100]
下附模板：

int find(int u){
    int ans = 0;
    while(u){
        ans += c[u];
        u -= u&-u;//去掉最后一个零
    }
    return ans;
}

求区间[l,r]即求[1,r] - [1,l - 1]

单点修改

注意：修改时应将其父亲，父亲的父亲...都修改
模板：

void add(int u,int x){//将第u个数增加x
    while(u <= n){
        c[u] += x;
        u += u&-u;//将最后一个零进一位
    }
}

谨记

相对于对于树状数组的两个功能，更重要的是将题意转化为树状数组能够实现的功能
如 树状数组2 的思路就是维护一个差分数组，将区间修改转化为两个区间端点的单点修改，将单点查询转化为查分数组的前缀和

好题

类似的树状数组题目还有 P1083 [NOIP2012 提高组] 借教室 、 P1908 逆序对 等

P3372 【模板】线段树 1

特别的，对于 P3372 【模板】线段树 1 中的区间修改、区间求和问题：
我们可以维护两个树状数组，
第一个如树状数组2中的，是一个查分的树状数组，这样就实现了区间修改功能
而在查询时，现将查分树状数组进行前缀和，实现单点查询，再维护一个树状数组，用以前缀和第一个树状数组的前缀和，这样就实现了区间查询的功能