树状数组

树状数组

1. 树状数组维护前缀和数组

1.1 单点修改，区间查询

核心伪代码

// lowbit：取出 x 的最低位 1（BIT 的核心）
int lowbit(int x){ return x & -x; }

// add(pos, delta)：a[pos] += delta
void add(int pos, long long delta){
    for(int i=pos;i<=n;i+=lowbit(i)){
        bit[i]+=delta;
    }
}

// sum(pos)：返回 a[1..pos] 的前缀和
long long sum(int pos){
    long long res=0;
    for(int i=pos;i>0;i-=lowbit(i)){
        res+=bit[i];
    }
    return res;
}

// range_sum(l,r) = sum(r)-sum(l-1)

区间总和

区间异或

void add(int pos,int v){
    for(int i=pos;i<=n;i+=lowbit(i)) bit[i]^=v;
}
int pref(int pos){
    int res=0;
    for(int i=pos;i>0;i-=lowbit(i)) res^=bit[i];
    return res;
}
// xor(l,r) = pref(r) ^ pref(l-1)

1.2 扫描线实现二维偏序计数（按一维排序扫描，另一维 BIT）

常见任务

• 给点 $(x,y)$，问有多少点满足 $x\le X$ 且 $y\le Y$
• 或者矩形询问：$x\le X$ 的点中，$y$ 落在某范围的计数



核心伪代码（离线）





// 1) 把点按 x 排序
sort(points by x);

// 2) 把询问按 X 排序
sort(queries by X);

// 3) 扫描：用指针把 x<=X 的点都加入 BIT（按 y 维更新）
int p=0;
for each query in queries increasing X:
    while(p < points.size() && points[p].x <= query.X){
        add(points[p].y, 1);        // BIT 维护 y 的计数前缀
        p++;
    }
    answer = sum(query.Y);          // 统计 y<=Y 的点数



------



1.3 区间内出现次数



维护一个前缀 $cnt$ 数组，判断其区间总和：
$$ cnt(l,r)=prefix(r)-prefix(l-1) $$



A) 多棵 BIT（按类别拆，比如 26 个字母/每行每列）



思路：每个类别一棵 BIT，查询区间出现次数就对那棵 BIT 做区间和。



// bit[c] 表示第 c 类的树状数组
// 修改：位置 pos 的类别从 old -> neu
add(bit[old], pos, -1);
add(bit[neu], pos, +1);

// 查询：区间 [l,r] 中类别 c 的次数
ans = sum(bit[c], r) - sum(bit[c], l-1);





B) 离线 last 出现位置 + BIT（求区间不同数个数）



思路（典型做法）：按右端点 $r$ 从小到大扫。
对每个值只在“最新出现的位置”放一个 $1$，旧位置变为 $0$。
这样 BIT 的前缀和表示“当前扫描到的 r 时，不同数的个数”。



// queries 按 r 排序
// last[val] 记录 val 上次出现位置
for r=1..n:
    val = a[r]
    if(last[val] != 0) add(last[val], -1)  // 旧位置清掉
    add(r, +1)                              // 新位置标 1
    last[val] = r

    // 对所有右端点等于 r 的询问 (l,r)
    // 不同数个数 = sum(r) - sum(l-1)



------



2. 树状数组维护差分数组





2.1 区间修改，单点查询



维护差分数组 $b$：

对区间 $[l,r]$ 加 $k$ 等价于
$$ b_l += k,\quad b_{r+1} -= k $$

单点值：
$$ a_i=\sum_{j=1}^{i} b_j $$



核心伪代码





// BIT 存差分 b
// range_add(l,r,k):
add(l, +k);
add(r+1, -k);

// point_query(i):
a_i = sum(i);          // 差分前缀就是原值



------



3. 树状数组维护计数数组





3.1 逆序对统计



核心：值域离散化后，扫一遍，维护“已出现的值的个数前缀”。

设当前值是 x（离散化后），之前出现过多少个 >x？
$$ \text{greater} = (i-1) - \text{count}(\le x) $$



核心伪代码





ans = 0;
for i=1..n:
    x = rank(a[i]);               // 离散化后的值
    ans += (i-1) - sum(x);        // 之前出现的总数 - <=x 的个数
    add(x, +1);                   // 记录当前值出现



------



3.2 动态查找第 $k$ 小/大



核心：BIT 维护每个值出现次数，然后在 BIT 上“二分找第 k 小”。



核心伪代码（BIT 二分）





// find_kth(k)：返回最小的 pos 使 sum(pos) >= k
int find_kth(int k){
    int pos = 0;
    // 这里的 LOG 取满足 2^LOG >= n 的最大 LOG
    for(int pw = highest_power_of_two; pw > 0; pw >>= 1){
        int nxt = pos + pw;
        if(nxt <= n && bit[nxt] < k){
            k -= bit[nxt];
            pos = nxt;
        }
    }
    return pos + 1;
}



------



3.3 求大于 $x$ 的个数



BIT 前缀表示 $\le x$ 的数量，所以：
$$ \#(x) = \#(\le \text{max}) - \#(\le x) $$
伪代码：



greater = sum(maxRank) - sum(rank(x));



------



3.4 是否存在范围内的数



很多“存在性”其实就是“计数是否 > 0”。

例如问区间内某类元素是否存在：
$$ cnt(l,r)=sum(r)-sum(l-1) $$
若 $cnt(l,r)0$ 则存在。

------



4. 树状数组维护前缀最值数组（特定条件）



下文以取最大值为例，取最小值反之即可。



4.1 适用条件



只能做这种情况：

• 更新：$a[i] = \max(a[i], v)$（只会变大，不会变小）
• 查询：$\max(a[1..x])$

4.2 核心伪代码（前缀 MAX）

// bit[i] 存的是某一段的最大值
void update(int pos, long long v){
    for(int i=pos;i<=n;i+=lowbit(i)){
        bit[i] = max(bit[i], v);
    }
}

long long query(int pos){
    long long res = -INF;
    for(int i=pos;i>0;i-=lowbit(i)){
        res = max(res, bit[i]);
    }
    return res;
}