第五讲树状数组与线段树
- 树状数组与线段树以及差分

第五讲树状数组与线段树

第五讲树状数组与线段树
- 树状数组与线段树以及差分

树状数组与线段树以及差分

例题1：动态求连续区间和

https://www.acwing.com/problem/content/1266/

给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。

输入格式

第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。

第二行包含 n 个整数，表示完整数列。

接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 bb）。

数列从 1 开始计数。

输出格式

输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。

数据范围

1≤n≤100000
1≤m≤100000
1≤a≤b≤n

mycode:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int w[N];
struct Node{
    int l,r;
    int sum; 
}tr[N*4];
void pushup(int u) {    //用子节点来更新当前结点信息 
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u,int l,int r) {    //在一段区间内初始化线段树 
    if(l==r) tr[u].l = l, tr[u].r = r, tr[u].sum = w[l];
    else{
        tr[u].l = l, tr[u].r = r;
        int mid = l + r >> 1;
        build(u << 1, l, mid),build(u << 1 | 1, mid +1, r);
        pushup(u);
    }
}
int query(int u,int l,int r) {    //查询 
    if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if(l <= mid) sum += query(u << 1, l, r);
    if(r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}
void modify(int u,int x,int v) {    //修改，加上一个数 
    if(tr[u].l == tr[u].r) tr[u].sum += v;
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}
int main() {
    int n,m;    //数的个数和操作次数
    cin >> n >> m;
    for(int i = 1; i <= n; i++) scanf("%d",&w[i]);
    build(1,1,n);
    while(m--) {
        int k,a,b;
        scanf("%d%d%d",&k,&a,&b);
        if(k==0) printf("%d\n",query(1,a,b));
        else modify(1,a,b);
    }
    return 0;
}

例题2：数星星

https://www.acwing.com/problem/content/1267/

天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。

如果一个星星的左下方（包含正左和正下）有 k 颗星星，就说这颗星星是 k 级的。

例如，上图中星星 5 是 3 级的（1,2,4 在它左下），星星 2,4 是 1 级的。

例图中有 1 个 0 级，2 个 1 级，1 个 2 级，1 个 3 级的星星。

给定星星的位置，输出各级星星的数目。

换句话说，给定 N 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

输入格式

第一行一个整数 N，表示星星的数目；

接下来 N 行给出每颗星星的坐标，坐标用两个整数 x,y表示；

不会有星星重叠。星星按 y 坐标增序给出，y 坐标相同的按 x 坐标增序给出。

输出格式

N 行，每行一个整数，分别是 0 级，1 级，2 级，……，N−1 级的星星的数目。

数据范围

1≤N≤15000
0≤x,y≤32000

输入样例：
5
1 1
5 1
7 1
3 3
5 5
输出样例：
1
2
1
1
0

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 32010, N = 15010;
int tr[M],level[N];
int lowbit(int x) {
    return x&-x;
}
void add(int x) {
    for(int i = x; i < M; i+=lowbit(i)) tr[i]++;
}
int query(int x) {
    int res = 0;
    for(int i = x; i; i-=lowbit(i)) res += tr[i];
    return res;
}
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x++;
        level[query(x)] ++;
        add(x);
    }
    for(int i = 0; i < n; i++) {
        printf("%d\n",level[i]);
    }
    return 0;
}

例题3：数列区间最大值

https://www.acwing.com/problem/content/1272/

输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y，要求你说出 X 到 Y 这段区间内的最大数。

输入格式

第一行两个整数 N,M 表示数字的个数和要询问的次数；

接下来一行为 N 个数；

接下来M 行，每行都有两个整数 X,Y。

输出格式

输出共 M 行，每行输出一个数。

数据范围

1≤N≤105
1≤M≤106
1≤X≤Y≤N
数列中的数字均不超过231−1

输入样例：
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
输出样例：
5
8

mycode:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 1e5+10;
int a[N];
struct Node{
    int l,r;
    int maxv;
}tr[4*N];
void build(int u, int l, int r) {
    //叶节点 
    if(l == r) tr[u] = {l,r,a[l]};
    else{
        tr[u] = {l,r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid+1, r);
        tr[u].maxv = max(tr[u<<1].maxv, tr[u<<1|1].maxv);
    }
}
int query(int u, int l, int r) {
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;
    int mid = tr[u].l + tr[u].r >> 1;
    int maxv = INT_MIN; 
    if(l <= mid) maxv = query(u << 1, l, r);
    if(r > mid) maxv = max(maxv,query(u << 1 | 1, l, r));
    return maxv;
}
int main() {
    int n,m;    //数字的个数，询问的次数
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    build(1,1,n);
    while(m--) {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",query(1,x,y));
    }
    return 0;
}

作业1：小朋友排队

https://www.acwing.com/problem/content/1217/

n 个小朋友站成一排。

现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。

开始的时候，所有小朋友的不高兴程度都是 0。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1，如果第二次要求他交换，则他的不高兴程度增加 2（即不高兴程度为 3），依次类推。当要求某个小朋友第k 次交换时，他的不高兴程度增加 k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

输入格式

输入的第一行包含一个整数 n，表示小朋友的个数。

第二行包含 n 个整数 H1,H2,…,Hn，分别表示每个小朋友的身高。

输出格式

输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

数据范围

1≤n≤100000
0≤Hi≤1000000

输入样例：
3
3 2 1
输出样例：
9
样例解释

首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。

mycode:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010;    //最多小盆友数,最高小盆友身高 
int n;    //小盆友个数 
int h[N],tr[N];    //小盆友的身高，树状数组维护身高i的人数
int sum[N];    //与第i个数相关的逆序对数量 
//树状数组三大函数
int lowbit(int x) {
    return x & -x;
}
void add(int x,int v) {
    for(int i = x; i < N; i += lowbit(i)) tr[i] += v;
}
int query(int x) {    //查询身高从1~i的人的总人数 
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%d",&h[i]), h[i]++;
    //位置在前，但是身高比当前大 
    for(int i = 1; i <= n; i++) {
        add(h[i],1);
        sum[i] = query(N-1) - query(h[i]);
    }
    //位置在后，但身高比当前小 
    memset(tr,0,sizeof tr);
    for(int i = n; i > 0; i--) {
        add(h[i],1);
        sum[i] += query(h[i] - 1);
    }
    LL res = 0;
    for(int i = 1; i <= n; i++) res += (LL)sum[i] * (sum[i] + 1) / 2;
    cout << res << endl;
    return 0;
}

作业2：油漆工击（待完成）

作业3：三体攻击（待完成）

作业4：螺旋折线

https://www.acwing.com/problem/content/1239/

如下图所示的螺旋折线经过平面上所有整点恰好一次。

对于整点 (X,Y)，我们定义它到原点的距离 dis(X,Y) 是从原点到 (X,Y) 的螺旋折线段的长度。

例如 dis(0,1)=3,dis(−2,−1)=9

给出整点坐标 (X,Y)，你能计算出 dis(X,Y) 吗？

输入格式

包含两个整数 X,Y。

输出格式

输出一个整数，表示 dis(X,Y)

数据范围

−109≤X,Y≤109

输入样例：
0 1
输出样例：
3

mycode:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int main() {
    int x,y;
    cin >> x >> y;
    //0特判
    if(x==0 && y==0) cout << 0 << endl;
    //判断在第几圈：找x和y的max的绝对值 
    int n = max(abs(x),abs(y));
    //判断在上下左右哪条边上
    long long st;
    if(x == -n) {    //在左边
        st = (LL)(2*n - 1) * (2*n - 1);
        cout << st + abs(y - (-n + 1));
    }else if(y == n) {    //在上边 
        st = (LL)(2*n - 1) * (2*n);
        cout << st + abs(x - (-n));
    }else if(x == n) {    //在右边 
        st = (LL)(2*n) * (2*n);
        cout << st + abs(y - n);
    }else if(y == -n) {    //在下边 
        st = (LL)(2*n) * (2*n+1);
        cout << st + abs(x - n) << endl;
    }
    return 0;
}

作业5：差分

https://www.acwing.com/problem/content/799/

输入一个长度为n的整数序列。

接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数n和m。

第二行包含n个整数，表示整数序列。

接下来m行，每行包含三个整数l，r，c，表示一个操作。

输出格式

共一行，包含n个整数，表示最终序列。

数据范围

1≤n,m≤100000
1≤l≤r≤n
−1000≤c≤1000
−1000≤整数序列中元素的值≤1000

输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2

mycode:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N],b[N];    //a为原数组(是维护b的前缀和数组)，b是差分数组 
int main() {
    int n,m;    //n个整数，m行命令
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        //b[i] = a[i] - a[i-1];    //构造差分数组
        b[i] += a[i];
        b[i+1] -= a[i];
    }
    while(m--) {
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        b[l] += c;
        b[r+1] -= c;
    }
    for(int i = 1; i <= n; i++){
        a[i] = a[i-1] + b[i];    //a为关于b的前缀和 
        printf("%d ",a[i]);
    }
    return 0;
}

作业6：差分矩阵

https://www.acwing.com/problem/content/800/

输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上c。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数n,m,q。

接下来n行，每行包含m个整数，表示整数矩阵。

接下来q行，每行包含5个整数x1, y1, x2, y2, c，表示一个操作。

输出格式

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

1≤n,m≤1000
1≤q≤100000
1≤x1≤x2≤n
1≤y1≤y2≤m
−1000≤c≤1000
−1000≤矩阵内元素的值≤1000

输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2

mycode:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N][N],b[N][N];    //原矩阵，差分矩阵 
void insert(int x1,int y1,int x2,int y2,int c) {    //添加进差分数组 
    b[x1][y1] += c;
    b[x1][y2+1] -= c;
    b[x2+1][y1] -= c;
    b[x2+1][y2+1] += c;
}
int main() {
    int n,m,q;    //n行m列，q个询问 
    cin >> n >> m >> q;    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d",&a[i][j]);
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--) {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        insert(x1,y1,x2,y2,c);
    }
    //根据差分b来算前缀a 
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];
        }
    }
    //输出a
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

5数装数组与线段树

第五讲 树状数组与线段树

树状数组与线段树以及差分

例题1：动态求连续区间和

输入格式

输出格式

数据范围

例题2：数星星

输入格式

输出格式

数据范围

输入样例：

输出样例：

例题3：数列区间最大值

输入格式

输出格式

数据范围

输入样例：

输出样例：

作业1：小朋友排队

输入格式

输出格式

数据范围

输入样例：

输出样例：

样例解释

作业2：油漆工击（待完成）

作业3：三体攻击（待完成）

作业4：螺旋折线

输入格式

输出格式

数据范围

输入样例：

输出样例：

作业5：差分

输入格式

输出格式

数据范围

输入样例：

输出样例：

作业6：差分矩阵

输入格式

输出格式

数据范围

输入样例：

输出样例：

第五讲树状数组与线段树