线段树算法讲解-配合洛谷p3372_区间最大值线段树luogu

1.简单介绍下什么是线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在序列中对应的位置，同时也能快速地修改序列中的一个节点的值。线段树每个节点都包含一个区间，以及该区间的一些信息。

线段树主要支持两种操作：

修改操作：单点更新或者区间更新。
查询操作：区间查询，例如区间最大值，最小值，区间和等。
线段树的构建、查询和修改的时间复杂度都是 O(logn)。

2.题目如下

题目描述

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

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]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
1
2
3
4
5
6
7

样例输出 #1

11
8
20
1
2
3

提示

对于 $30\%$ 的数据：$n\le 8$，$m\le 10$。
对于 $70\%$ 的数据：$n\le {10}^3$，$m\le {10}^4$。
对于 $100\%$ 的数据：$1\le n,m\le {10}^5$。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。

【样例解释】

3.题目解析

这道题目是一个典型的线段树应用题。我们需要对一个序列进行两种操作，一种是更新操作，一种是查询操作。更新操作是将某个区间的所有数加上一个值，查询操作是求出某个区间的所有数的和。这两种操作都可以通过线段树在 O(logn) 的时间复杂度内完成。

4.解题思路

解析完题目要求后，接下来就可以使用线段树来解决这个问题了。线段树的每个节点表示一个区间的和，当我们需要更新一个区间的时候，我们只需要找到包含这个区间的节点，更新这个节点的值，然后递归更新它的子节点的值。当我们需要查询一个区间的和的时候，我们只需要找到包含这个区间的节点，返回这个节点的值即可。

5.代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5+5;
ll a[maxn],tree[4*maxn],lazy[4*maxn];

void build(int node,int start,int end){
    if(start == end){
        tree[node] = a[start];
    }
    else{
        int mid = (start + end) / 2;
        build(2*node,start,mid);
        build(2*node+1,mid+1,end);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}

void update(int node,int start,int end,int l,int r,ll val){
    if(lazy[node] != 0){
        tree[node] += (end - start + 1) * lazy[node];
        if(start != end){
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if(start > end or start > r or end < l)return;
    if(start >= l and end <= r){
        tree[node] += (end - start + 1) * val;
        if(start != end){
            lazy[node*2] += val;
            lazy[node*2+1] += val;
        }
        return;
    }
    int mid = (start + end) / 2;
    update(node*2,start,mid,l,r,val);
    update(node*2+1,mid+1,end,l,r,val);
    tree[node] = tree[node*2] + tree[node*2+1];
}

ll query(int node,int start,int end,int l,int r){
    if(start > end or start > r or end < l)return 0;
    if(lazy[node] != 0){
        tree[node] += (end - start + 1) * lazy[node];
        if(start != end){
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if(start >= l and end <= r)return tree[node];
    int mid = (start + end) / 2;
    ll p1 = query(node*2,start,mid,l,r);
    ll p2 = query(node*2+1,mid+1,end,l,r);
    return (p1 + p2);
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1,1,n);
    while(m--){
        int type;
        cin >> type;
        if(type == 1){
            int x, y;
            ll k;
            cin >> x >> y >> k;
            update(1,1,n,x,y,k);
        }
        else{
            int x, y;
            cin >> x >> y;
            cout << query(1,1,n,x,y) << endl;
        }
    }
    return 0;
}

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

我们首先定义了一个线段树，然后通过 build 函数构建线段树。update 函数用于更新线段树的节点，query 函数用于查询线段树的节点。在主函数中，我们读入数据，然后根据操作类型进行相应的操作。如果是更新操作，我们调用 update 函数，如果是查询操作，我们调用 query 函数。

编译运行，答案正确。下面我详细解释一下各个函数的作用：

1.build 函数：这个函数用于构建线段树。它首先检查当前区间是否只包含一个元素，如果是，那么就将这个元素的值赋给对应的节点。否则，它将区间分为两部分，然后递归地构建左子树和右子树。最后，将当前节点的值设置为左子树和右子树的值的和。
2. update 函数：这个函数用于更新线段树的节点。它首先检查当前节点是否有延迟更新的值，如果有，那么就将这个值加到当前节点的值上，然后将这个值传递给子节点。然后，它检查当前区间是否与更新区间有交集，如果没有，那么就直接返回。否则，如果当前区间完全包含在更新区间内，那么就将更新值加到当前节点的值上，然后将更新值传递给子节点。如果当前区间和更新区间只有部分重叠，那么就递归地更新左子树和右子树，然后将当前节点的值设置为左子树和右子树的值的和。
3. query 函数：这个函数用于查询线段树的节点。它首先检查当前节点是否有延迟更新的值，如果有，那么就将这个值加到当前节点的值上，然后将这个值传递给子节点。然后，它检查当前区间是否与查询区间有交集，如果没有，那么就直接返回 0。否则，如果当前区间完全包含在查询区间内，那么就直接返回当前节点的值。如果当前区间和查询区间只有部分重叠，那么就递归地查询左子树和右子树，然后返回两者的和。
4. main 函数：这个函数首先读入数据，然后构建线段树。然后，它读入操作，根据操作类型进行相应的操作。如果是更新操作，那么就调用 update 函数。如果是查询操作，那么就调用 query 函数，然后输出结果。

运行结果

最后当然也是全都A了

希望能帮到你，我们一起学习、进步。