树状数组简介

以下讲解主要参考：

AcWing 241. 楼兰图腾 题解

bilibili 完全理解并深入应用树状数组

OI Wiki 树状数组

树状数组可以用于解决部分单点修改 区间查询的问题

树状数组实现了：单点修改： Olog⁡nO_{\log{n}} 区间查询： Olog⁡nO_{\log{n}}

树状数组是将区间和划分为一种特殊的树状结构，通过对树的叶节点的查找而确定单点的值

树状结构的建立：

  1. 构建一个数组tr[x]保存以x结尾长度为x的lowbit值，这样就可以由特殊的区间和定义通过数组构建一个树状结构

    树状数组-结点覆盖的长度

  2. 我们无法简单地通过父节点的得到子节点（其直接子节点的数量都不是定值），单数对于tr[x]其父节点就是tr[x+lowbit(x)]（x+lowbit(x)是其lowbit值正好是比lowbit(x)大的最小值）

  3. 树的深度就是最大的lowbit值所在的位数也就是 log⁡2n + 1\log_2{n}\ +\ 1

基本操作：单点修改 & 区间查询

  1. lowbit(int x)操作

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

  2. 单点修改：add(int x,int k)将序列中的a[x]加上一个k

    找到a[x]的所有父节点，然后将其加上k

    1
    2
    3
    4
    5
    void add(int x, int k){
        for(int i = x; i <= n; i+=lowbit(i)){
            tr[i] += k;
        }
    }

    树状数组-add.png

  3. 区间查询：ask(int x)查找[1, x]的区间和

    根据对tr[]的定义，tr[x]所代表的区间和长度为lowbit(x)而x-lowbit(x)就是第一个与tr[x]连接的下一个区间和的开头

    1
    2
    3
    4
    5
    6
    7
    int ask(int x){
        int sum = 0;
        for(int i = x; i; i -= lowbit(i)){
            sum += tr[i];
        }
        return sum;
    }

    树状数组-ask.png

区间修改 & 单点查询

然后我们就可以将树状数组利用差分的思想进行扩展，就可以将单点修改 区间查询转换为区间修改和单点查询了

区间修改 & 区间查询

假设我们要对数组arr[]进行操作，而数组b[]是数组arr[]的差分数组，通过这个差分数组我们可以很容易地对arr[]进行区间修改，可是我们要如何进行区间查询呢？

我们可以将原问题公式化来看：求 ∑i=1rarr[i]\sum^r_{i=1}{arr[i]}

\begin{align*}\label{2} &\quad\sum^r_{i=1}{arr[i]}\\ &=\sum^r_{i=1}{\sum^i_{j=i}{b[j]}}\\ &=\sum^r_{i=1}{b[i]\ \times\ (r-i+1)}\\ &=(r+1)\times\sum^r_{i=1}{b[i]}\ -\ \sum^r_{i=1}{b[i]\times i} \end{align*}

这里可以通过画图更形象地展示这个变换的过程：

未命名绘图

左边的值应该等于右边红色部分的值，而蓝色部分是我们为了构造出规整的结构而填补上去的值，所以要求 ∑i=1rarr[i]\sum^r_{i=1}{arr[i]} 就等价于大的方阵减去蓝色部分，而蓝色部分如果竖向看的话就会发现其实就是 ∑i=1rb[i]×i\sum^r_{i=1}{b[i]\times i}​ ，所以也能得到数学推导出来的结论

于是我们就可以通过维护两个差分树状数组tr1[]和tr2[]来求区间和

区间修改：我们每次修改的时候需要同时修改tr1[]和tr2[]，并且要注意这里的差分数组代表的含义有所不同

1
2
3
4
5
6
7
8
9
10
void add(int k, int v) {
  int v1 = k * v;
  for (int i = k; i <= n; i += lowbit(i)) {
    tr1[i] += v, tr2[i] += v1;
  }
}

void add1(int l, int r, int v) {
  add(l, v), add(r + 1, -v);  // 将区间加差分为两个前缀加
}

区间查询：我们根据已经得到的公式去计算就好

1
2
3
4
5
6
7
8
9
10
long long getsum(int *tr, int k) {
  long long ans = 0;
  for (int i = k; i; i -= lowbit(i)) {
    ans += tr[i];
  }
  return ans;
}
long long getsum1(int l, int r) {
  return (r + 1ll) * getsum(tr1, r) - 1ll * l * getsum(tr1, l - 1) - (getsum(tr2, r) - getsum(tr2, l - 1));
}

应用

题目1 楼兰图腾

题面描述：在完成了分配任务之后，西部314来到了楼兰古城的西部。

相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(‘V’)，一个部落崇拜铁锹(‘∧’)，他们分别用V和∧的形状来代表各自部落的图腾。

西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。

西部314认为这幅壁画所包含的信息与这N个点的相对位置有关，因此不妨设坐标分别为(1,y1),(2,y2),…,(n,yn),其中y1~yn是1到n的一个排列。

西部314打算研究这幅壁画中包含着多少个图腾。

如果三个点(i,yi),(j,yj),(k,yk)满足1 ≤ i < j < k ≤ n 且 y1 > yj , yj < yk，则称这三个点构成V图腾;

如果三个点(i,yi),(j,yj),(k,yk)满足1 ≤ i < j < k ≤ n 且 y1 < yj , yj > yk，则称这三个点构成∧图腾;

西部314想知道，这n个点中两个部落图腾的数目。

因此，你需要编写一个程序来求出V的个数和∧的个数。

原题链接：AcWing 241. 楼兰图腾

解题思路：

  1. 转变思路，这个对于每个位置上的数a[i]就是找到其左边比a[i]大的数x和右边比a[i]大的数y，根据组合原理以a[i]为中间值的V型结构的数量就是x * y，∧型同理
  2. 于是我们就可以从左往右和从右往左两遍遍历就可以得到两份数字Greater[]和Lower[]，这里需要处理的是单点修改（添加已经遍历到的数值）和区间查询（从已经遍历的数中找到大于和a[i]的数的个数）的问题，于是我们可以使用树状数组来处理这样的问题
  3. 第一遍遍历，每一次遍历到某个数字就将比这个数大的数字也就是在[y+1, n]（y是表示遍历到的数的数值大小）之间的数保存到Greater[i]中表示从这个数左（右）边比这个数大的数有Greater[i]个，同时将[1, y-1]之间的数保存到Lower[i]中；这里的[y+1, n]之间的数可以用ask(n)-ask(y)表示，而ask[y-1]可以表示[1, y-1]之间的数的数量，最后将这个数添加到树状数组中表示这个数已经被遍历到了add(y, 1)
  4. 同样的第二遍遍历需要从相反的方向开始遍历即可，然后得到的数直接与先前的数相乘保存到结果中即可
  5. 这里需要注意的一点就是数值范围和数据范围是相同的都不是特别的大，所以不需要离散化，如果明显数值范围过大还需要离散化，并且这里的离散化数必须考虑数据的相对大小关系

完整代码：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 200010;

int n;
int a[N];
int tr[N];
int Greater[N], Lower[N];

int lowbit(int x){
    return x & -x;
}

void add(int x, int k){
    for(int i = x; i <= n; i += lowbit(i)){
        tr[i] += k;
    }
}

int ask(int x){
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)){
        sum += tr[i];
    }
    return sum;
}

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    for(int i = 1; i <= n; i++){
        int y = a[i];
        Greater[i] = ask(n) - ask(y);
        Lower[i] = ask(y-1);
        add(y, 1);
    }
    
    memset(tr, 0, sizeof tr);
    LL ans_A = 0, ans_V = 0;
    
    for(int i = n; i; i--){
        int y = a[i];
        ans_V += (LL)Greater[i] * (ask(n)-ask(y));
        ans_A += (LL)Lower[i] * ask(y-1);
        add(y, 1);
    }
    
    cout<<ans_V<<" "<<ans_A;
    return 0;
}

题目2 一个简单的整数问题

题面描述：给定长度为N的数列A，然后输入M行操作指令。

第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。

第二类指令形如“Q X”，表示询问数列中第x个数的值。

对于每个询问，输出一个整数表示答案。

原题链接：AcWing 242. 一个简单的整数问题

解题思路：

  1. 这就是一个比较显然的差分树状数组的使用，只需要知道区间修改是通过add(l, c); add(r+1, -c)得到，而单点查询则是通过ask(x)得到即可（对此不熟悉的化可以去看一下前缀和数组和差分数组的相关知识）

完整代码：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int a[N];
LL tr[N];

int lowbit(int x){
    return x & -x;
}

void add(int x, int c){
    for(int i = x; i <= n; i += lowbit(i)){
        tr[i] += c;
    }
}

LL ask(int x){
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)){
        sum += tr[i];
    }
    return sum;
}

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    for(int i = 1; i <= n; i++) add(i, a[i]-a[i-1]);
    
    while(m--){
        char op[2];
        int l, r, d;
        scanf("%s%d", op, &l);
        if(op[0] == 'C'){
            scanf("%d%d", &r, &d);
            add(l, d);
            add(r+1, -d);
        }
        else{
            printf("%lld\n", ask(l));
        }
    }
    return 0;
}

题目3 一个简单的整数问题2

题面描述：给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

2、“Q l r”，表示询问 数列中第 l~r 个数的和。

对于每个询问，输出一个整数表示答案。

原题链接：AcWing 243. 一个简单的整数问题2

解题思路：

  1. 这题同样是继承上一题的模板题，主要考察对树状数组的扩展中的区间修改区间查询的掌握

完整代码：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long LL;
const int N = 100010;

int n, m;
int a[N];
LL tr1[N]; //维护b[i]的前缀和
LL tr2[N]; //维护b[i]*i的前缀和

inline int lowbit(int x){
    return x&-x;
}

void add(int x, LL c){
    LL c2 = c*x;
    for(int i = x; i <= n; i+=lowbit(i)){
        tr1[i] += c, tr2[i] += c2;
    }
}

LL getSum(LL tr[], int x){
    LL ans = 0;
    for(int i = x; i; i-=lowbit(i)){
        ans += tr[i];
    }
    return ans;
}

void add1(int l, int r, LL c){
    add(l, c);
    add(r+1, -c);
}

LL getSum1(int x){
    return (x+1)*getSum(tr1, x) - getSum(tr2, x);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++){
        int b = a[i]-a[i-1];
        add(i, b);
    }
    while(m--){
        char op[2];
        int l, r, d;
        scanf("%s%d%d", op, &l, &r);
        if(op[0] == 'Q'){
            printf("%lld\n", getSum1(r)-getSum1(l-1));
        }
        else{
            scanf("%d", &d);
            add1(l, r, d);
        }
    }
    return 0;
}

题目4 谜一样的牛

题面描述：有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高；现在这n头奶牛站成一列，已知第i头牛前面有Ai头牛比它低，求每头奶牛的身高。

原题链接：AcWing 244. 谜一样的牛

解题思路：

  1. 先就最朴素的算法来看，我们先从最后一头牛入手，于是可以知道最后一头牛看到的比它矮的牛的数量加1就是他自己的排名了，同样的找到倒数第2头牛它前面的比它矮的牛的数量中就是它目前的排名了，但是要注意的就是这个排名是需要去除已经知道排名的最后一头牛以后的排名，其后便以此类推
  2. 于是我们可以构建一个所有牛的个数长度的数组用0和1的值来表示这头牛是否需要考虑，然后就可以将这样的问题抽象成：从后往前扫描的单点修改（删除掉已经确定排名的牛）和区间查询（查找还未确定排名的牛中排名为a[i]+1的牛，这里的a[i]是指牛i前面比它矮的牛的数量）
  3. 这里的区间查找具有二向性于是我们就可以结合二分的方式去找到这个排名

完整代码：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100010;

int n;
int h[N];
int ans[N];
int tr[N];

inline int lowbit(int x){
    return x&-x;
}

void add(int x, int c){
    for(int i = x; i <= n; i+=lowbit(i)){
        tr[i] += c;
    }
}

int sum(int x){
    int ans = 0;
    for(int i = x; i; i-= lowbit(i)){
        ans += tr[i];
    }
    return ans;
}

int main(){
    scanf("%d", &n);
    for(int i = 2; i <= n; i++) scanf("%d", &h[i]);
    for(int i = 1; i <= n; i++) tr[i] = lowbit(i);
    for(int i = n; i; i--){
        int k = h[i]+1;
        int l = 1, r = n;
        while(l < r){
            int m = l+r>>1;
            if(sum(m) < k) l =m+1;
            else r = m;
        }
        ans[i] = r;
        add(r, -1);
    }
    
    for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}

副栏

关于单点修改区间查询和单点更新区间更新的问题可以使用到的方法太多了但是各种方法的关注点都不太一样，所以打算做个总结。副栏肯定写不完所以会开一个新的文章链接就贴在这（先在这立个flag）