跳转至

树状数组

前半部分由 \(KccoT\) 独家为您呈现

一维树状数组

一种数据结构，可以实现单点修改和区间查询操作，运用类似前缀和的思想

\(lowbit\) 算法

表示一个数 \(n\) 在二进制表示下最低位的 \(1\) 和后面所有的 \(0\) 组成的数

(证明不会...)

代码实现

1
2
3
int lowbit(int x){
    return x & (-x);
}

\(lowbit\) 在树状数组中的应用是拆分区间

例如 将 \(7\) 使用 \(lowbit\) 算法拆分

\(lowbit(7) = 1,x=7-lowbit(7)=7-1=6,区间[7,7]\)

\(lowbit(6)=2,x=6-lowbit(6)=6-2=4，区间[5,6]\)

\(lowbit(4)=4,区间[1,4]\)

我们可以发现运用 \(lowbit\) 算法可以将 \([1,7]\) 区间拆分成三个区间

从上述过程中我们可以发现规律，每一个区间的左端点都为 \(x-lowbit(x)+1\) ,右端点为 \(x\) ，因此每个拆分出来的区间为 \([x-lowbit(x)+1,x]\)

性质

树的深度为 \(log_n\)

每个节点的父节点是 \([x+lowbit(x)]\)

操作

单点修改

在树状数组上更改某一个的点值，包含他的区间也同时要修改维护的区间值，运用上述性质二，逐层修改即可

1
2
3
4
5
6
void add(int x, int y){
    while(x <= n){
        c[x] += y;
        x += lowbit(x);
    }
}

区间查询

求区间和时，将其所包含的小区间的值加起来即可，同单点修改，运用上述性质二，逐层向下累加即可

1
2
3
4
5
6
7
8
9
int ask(int x){
    //求[1,x]的区间值
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

差分优化

可实现区间修改+单点查询

维护一个差分数组，对于差分数组维护树状数组即可

修改时在x加，y+1减即可 (即 add(x,k) , add(y+1,-k) )

求逆序对

运用树状数组求逆序对需要运用到离散化，将原数组离散化

循环每个 \(a[i]\)，每次在a[i]在离散化数组中出现的位置上加 \(1\)，\(i-sum(lowerbound(lsh + 1, lsh + 1 + k, a[i]) - lsh)\) 表示前面有几个数大于 \(a[i]\) 就是组成逆序对的个数

1
2
3
4
5
6
sort(lsh + 1, lsh + 1 + n);
int k = unique(lsh + 1, lsh + 1 + n) - lsh;//离散化 
for(int i = 1 ; i <= n ; i++){
    add(lower_bound(lsh + 1, lsh + 1 + k, a[i]) - lsh, 1);
    ans += i - sum(lower_bound(lsh + 1, lsh + 1 + k, a[i]) - lsh);
}

二维树状数组

差分

树状数组其实就是运用差分的思想，所以差分在树状数组的应用中很重要

一维差分

有一个数组a，其差分数组为d，前缀和数组为s

\[ \begin{equation} \begin{aligned} d[i]&=a[i]-a[i-1],d[1]=a[1] \\a[i]&=d[1]+d[2]+d[3]+\dots+d[i] \\s[i]&=a[1]+a[2]+a[3]+\dots+a[i] \\&=d[1]+(d[1]+d[2])+(d[1]+\dots+d[i]) \\&=d[1]*i+d[2]*(i-1)+d[3]*(i-2)+\dots+d[i]*1 \end{aligned} \end{equation} \]

一维差分的操作较为简单 \(把[a,b]+v\) \(d[a]+v,d[b+1]-v\) 即可

二维差分

其规律与一维差分类似

\[ \begin{equation} \begin{aligned} s[x][y]&=\sum_{i=1}^{x}\sum_{j=1}^{y}\sum_{h=1}^{i}\sum_{w=1}^{j}d[h][w] \\&=\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]*(x-i+1)*(y-j+1) \\&=\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]*(xy+x+y+1)-d[i][j]*i*(y+1)-d[i][j]*j*(x+1)+d[i][j]*i*j \end{aligned} \end{equation} \]

由此规律可知我们需要在二维树状数组上维护四个差分数组 \(A=d[i][j],B=d[i][j]*i,C=d[i][j]*j,D=d[i][j]*i*j\)

求和操作即为上述规律

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct BIT{//二维树状数组 
    int s[maxn][maxn];
    void change(int x, int y, int v){
        for(int i = x ; i <= n ; i += lowbit(i)){
            for(int j = y ; j <= m ; j += lowbit(j)){
                s[i][j] += v;
            }
        }
    }
    int query(int x, int y){
        int ans = 0;
        for(int i = x ; i >= 0 ; i -= lowbit(i)){
            for(int j = y ; j >= 0 ; j -= lowbit(j)){
                ans += s[i][j];
            }
        }
        return ans;
    }
}A, B, C, D;

void add(int x, int y, int v){//维护四个差分 
    A.change(x, y, v);
    B.change(x, y, v * x);
    C.change(x, y, v * y);
    D.change(x, y, v * x * y);
}

int sum(int x, int y){
    return A.query(x, y) * (x + y + x * y + 1) - B.query(x, y) * (x + 1) - C.query(x, y) * (y + 1) + D.query(x, y);
}

在二维差分区间加的操作中不同于一维差分

操作\([(a,b),(c,d)]+v\) 需要 \(d[a][b]+v,d[a][b+1]-v,d[c+1][b]-v,d[c+1][d+1]+v\) 

1
2
3
4
add(a, b, v);
add(c + 1, d + 1, -v);
add(a, d + 1, -v);
add(c + 1, b, -v);

二维差分求和操作思想等同于区间加思想

求 \([(a,b),(c,d)]\) 矩阵中的数字和 \(sum(c,d) - sum(c,b-1)-sum(a-1,d)+sum(a+1,b+1)\) 即可

1
sum(c, d) - sum(c, b - 1) - sum(a - 1, d) + sum(a - 1, b - 1)

补充

(以下内容均有蒟蒻 \(LonelyStar\) 补充，可能会出现码风不同的情况)

为什么要学树状数组

大家可能有疑惑：既然我们有功能更多的线段树了，何必在学树状数组捏？ 那么来看看树状数组有什么优点叭

树状数组相对于线段树的优点

  1. 树状数组在空间上所需更小，线段树需要4倍空间，而树状数组只需要1倍
  2. 树状数组的常数更小，跑的比线段树要快（例如：这是线段树，这是树状数组）我们能明显看出来树状数组要快许多
  3. 最重要的一点 ，ta超好写！！！（人话：偷懒），但在日常写代码，模拟赛甚至比赛时，树状数组要比线段树要方便许多，而且如果出错的话也很好调

难道树状数组真的没有再多，哪怕一点点功能嘛

欸，虽然树状数组至今无法实现如区间乘除，区间最大最小，但是，我们还是能在多做一点点的！！！

上面已经提到过单点修改+区间查询以及区间修改+单点查询，但这两种显然无法直接做到区间修改+区间查询

区间修改+区间查询！！！！

这种写法很少见，也挺邪门，很多人以及许多 \(dalao\) 都会建议直接上功能更强的线段树，但看在ta第3个优点上，还是值得一学的

想要实现，还是离不开差分和前缀和的思路

为了方便理解，让我们形象理解一下

比如对于一个数列 {1,3,6,10,15}，易得ta的差分数组为 {1,2,3,4,5}，如果这是我们要统计该数列的总和，可以发现对应的差分数组中的第i位分别调用了{5,4,3,2,1}次 （总之思路大概就是这个思路，太细节的我也不好证qwq）

对于这种思路，属于是用思维量来换的，其实大可以直接硬背板子~（因为尊嘟好背awa），那么就直接上代码叭

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void add(int x,int k){
    for(int i=x;i<=n;i+=lowbit(i)){
        t1[i]+=k;
        t2[i]+=k*x;
    }
}

void range_add(int l,int r,int k){
    add(l,k);
    add(r+1,-k);
}

int ask(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i)){
        ans+=(x+1)*t1[i]-t2[i];
    }
    return ans;
}

int range_ask(int l,int r){
    return ask(r)-ask(l-1);
}

(可以看出来真的要好背些)

区间修改+区间查询的注意事项

在我们使用该操作的时候，进行单点修改+单点查询的时候依然要使用 range_add 以及 range_ask ，不然会挂掉的awa