前言:

好久没更新我的博客了，最近变得好懈怠了。我收回之前说的话，蓝桥杯过后有icpc等着我，算法是要继续学的。

学算法感觉成就感挺高的，虽然很难也需要天赋，但是我会继续坚持下去的，加油。

当询问一段区间的和你可能会想到前缀和处理。当修改一段区间的值或只修改数组一个值，你可能会想到差分。

那么问题便来了，我若都要进行，而且操作很多次呢，是不是前缀和的处理以及差分处理会变得十分无助且无用。

所以接下来我们将用一个新的数据结线段树解决这些问题。

概述:

线段树是一种基于树形结构实现的数据结构，主要用于高效处理区间查询问题。

具体而言，线段树可以对一个固定大小的数组进行预处理，用于支持多次对其中某个区间的查询和更新操作。线段树的叶子节点对应于数组中的单个元素，而非叶子节点代表了若干个元素的区间。

在处理区间查询问题时，可以通过操作线段树上与查询区间相交的结点，并将这些结点的信息组合起来得到查询结果。在处理区间更新操作时，可以通过操作线段树上与更新区间相交的结点，并将这些结点的信息更新、传递得到更新结果。

因此，线段树主要被用于处理具有区间查询和区间更新操作的数据结构，如动态数组、序列、链表、二维矩阵等。经过优化的线段树能够在 O(logn)的时间内进行单次查询和更新操作，具有较高的时空效率。

线段树常见的模板:

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
63
64
65
66
67
68
69
70
71
72
73
typedef long long ll;
const int MAXN=100005;
int a[MAXN];
struct Node{
    int l,r,tag;//l，r表示该节点表示的若干元素的区间，tag用来记录修改的值
    ll sum,mx;//sum为子孙的和，mx为区间的最大值。
}tree[MAXN<<2];//线段树大小开到数组的四倍
inline int tl(int p){return p<<1;}//左孩子

inline int tr(int p){return p<<1|1;}//右孩子

inline void push_up(int p){//将p底下的子孙的值总和起来
    tree[p].sum=tree[tl(p)].sum+tree[tr(p)].sum;
}
inline void push_down(int p){//将p的tag修改值传递下去，同时子孙的数据也要改变
    if(tree[p].tag){//如果p更新过数据
        int tag=tree[p].tag;
        tree[p].tag=0;
        tree[tl(p)].tag+=tag;
        tree[tr(p)].tag+=tag;
        tree[tl(p)].mx+=tag;
        tree[tr(p)].mx+=tag;
        tree[tl(p)].sum+=(tree[tl(p)].r-tree[tl(p)].l+1)*tag;
        tree[tr(p)].sum+=(tree[tr(p)].r-tree[tr(p)].l+1)*tag;
    }
}
void build(int p,int l,int r){//建立线段树
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].sum=a[l];
        tree[p].mx=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(tl(p),l,mid);//建立左树
    build(tr(p),mid+1,r);//建立右树
    push_up(p);
}
void update(int p,int l,int r,int val){
    if(l<=tree[p].l&&r>=tree[p].r){//如果有一段区间被包含在要修改的区间，直接进行修改，不需要从子树的左右子树找
        tree[p].tag+=val;
        tree[p].sum+=(tree[p].r-tree[p].l+1)*val;
        tree[p].mx+=val;
        return;
    }
    push_down(p);//将更改的信息往子树传递
    int mid=(tree[p].l+tree[p].r)>>1;
    if(mid>=l)update(tl(p),l,r,val);//如果区间与要修改的区间左边有交集，从左子树找
    if(mid<r)update(tr(p),l,r,val);//如果区间与要修改的区间右边有交集，从右子树找
    push_up(p);//更新父亲
}
ll query_sum(int p,int l,int r){
    if(l<=tree[p].l&&r>=tree[p].r){//如果该区间刚好在要查询的区间中直接返回sum
        return tree[p].sum;
    }
    push_down(p);//遍历子树时，要将tag的信息往下传
    int mid=(tree[p].l+tree[p].r)>>1;
    ll sum=0;
    if(mid>=l)sum+= query_sum(tl(p),l,r);//如果区间与要查询的区间左边有交集，从左子树找
    if(mid<r)sum+= query_sum(tr(p),l,r);//如果区间与要查询的区间右边有交集，从右子树找
    return sum;//返回答案
}
ll query_max(int p,int l,int r){
    if(l<=tree[p].l&&r>=tree[p].r){//如果该区间刚好在要查询的区间中直接返回mx
        return tree[p].mx;
    }
    push_down(p);//和上面的一样
    int mid=(tree[p].l+tree[p].r)>>1;
    ll res=0;
    if(mid>=l)res=res> query_max(tl(p),l,r)?res:query_max(tl(p),l,r);//如果区间与要查询的区间左边有交集，从左子树找
    if(mid<r)res=res>query_max(tr(p),l,r)?res:res>query_max(tr(p),l,r);//如果区间与要查询的区间右边有交集，从右子树找
    return res;
}

实践

题目:P3372 【模板】线段树 1

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 k。
  2. 求出某区间每一个数的和。

第一行包含两个整数 n, m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 [x, y] 内每个数加上 k。
  2. 2 x y：输出区间 [x, y] 内每个数的和。

代码实现:

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100005;
int a[MAXN];
int n,m;
struct Node{
    int l,r,tag;//l，r表示该节点表示的若干元素的区间，tag用来记录修改的值
    ll sum,mx;//sum为子孙的和，mx为区间的最大值。
}tree[MAXN<<2];//线段树大小开到数组的四倍
inline int tl(int p){return p<<1;}//左孩子

inline int tr(int p){return p<<1|1;}//右孩子

inline void push_up(int p){//将p底下的子孙的值总和起来
    tree[p].sum=tree[tl(p)].sum+tree[tr(p)].sum;
}
inline void push_down(int p){//将p的tag修改值传递下去，同时子孙的数据也要改变
    if(tree[p].tag){//如果p更新过数据
        int tag=tree[p].tag;
        tree[p].tag=0;
        tree[tl(p)].tag+=tag;
        tree[tr(p)].tag+=tag;
        tree[tl(p)].mx+=tag;
        tree[tr(p)].mx+=tag;
        tree[tl(p)].sum+=(tree[tl(p)].r-tree[tl(p)].l+1)*tag;
        tree[tr(p)].sum+=(tree[tr(p)].r-tree[tr(p)].l+1)*tag;
    }
}
void build(int p,int l,int r){//建立线段树
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].sum=a[l];
        tree[p].mx=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(tl(p),l,mid);//建立左树
    build(tr(p),mid+1,r);//建立右树
    push_up(p);
}
void modify(int p,int l,int r,int val){
    if(l<=tree[p].l&&r>=tree[p].r){//如果有一段区间被包含在要修改的区间，直接进行修改，不需要从子树的左右子树找
        tree[p].tag+=val;
        tree[p].sum+=(tree[p].r-tree[p].l+1)*val;
        tree[p].mx+=val;
        return;
    }
    push_down(p);//将更改的信息往子树传递
    int mid=(tree[p].l+tree[p].r)>>1;
    if(mid>=l)modify(tl(p),l,r,val);//如果区间与要修改的区间左边有交集，从左子树找
    if(mid<r)modify(tr(p),l,r,val);//如果区间与要修改的区间右边有交集，从右子树找
    push_up(p);//更新父亲
}
ll query_sum(int p,int l,int r){
    if(l<=tree[p].l&&r>=tree[p].r){//如果该区间刚好在要查询的区间中直接返回sum
        return tree[p].sum;
    }
    push_down(p);//遍历子树时，要将tag的信息往下传
    int mid=(tree[p].l+tree[p].r)>>1;
    ll sum=0;
    if(mid>=l)sum+= query_sum(tl(p),l,r);//如果区间与要查询的区间左边有交集，从左子树找
    if(mid<r)sum+= query_sum(tr(p),l,r);//如果区间与要查询的区间右边有交集，从右子树找
    return sum;//返回答案
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    build(1, 1, n);
    while (m--) {
        int op, l, r, k;
        scanf("%d %d %d", &op, &l, &r);
        if (op == 1) {
            scanf("%d", &k);
            modify(1, l, r, k);
        }
        else {
            printf("%lld\n", query_sum(1, l, r));
        }
    }
    return 0;
}