大家好，欢迎来到IT知识分享网。
目录
1.2 简单线段树（无pushdown）——区间查询，单点修改
一、线段树介绍
1.1 什么是线段树
线段树是一种能把一些对于区间（或者线段）的修改、维护，从O（n）的时间复杂度变为O（logn）的工具。
线段树是一个完全二叉树，我们可以用堆来存，可以用一维数组来存。对于一个长度为8的线段，可以这样表示
每一个线段[L, R]，代表区间[L, R]的和，如[1,4]就代表1~4的和
如果用一维数组来存，下标（蓝色）如下：
由此我们可以知道，对于下标为x的线段，有以下性质
以数组a为例： 父节点：a[x/2] 或者 a[x >> 1] 左儿子：a[2 * x] 或者 a[x << 1] 右儿子：a[2 * x + 1] 或者 a[x << 1 | 1] 父节点的属性可以由2个儿子来更新，以求和为例： 父节点的值 = 2个儿子的和 a[x].sum = a[x << 1].sum + a[x << 1 | 1].sum1.2 简单线段树（无pushdown）——区间查询，单点修改
题目描述
题目链接：1275. 最大数 – AcWing题库
思路分析
建立操作
根据这些，我们就可以建立一个线段树，我们一般是通过设置一个结构体来储存需要的信息，一般存的信息，需要判断一下是否能根据2个子区间算出来，数组最低要开4N，简单举一个例子：
struct node{ int l, r; int Max; //区间[l, r]的最大值 }tr[4 * N];以下是建立线段树操作
void build(int u, int l, int r)//u是当前节点位置,l、r为区间边界 { tr[u] = {l, r}; //存下当前节点左右边界 if(l == r) //如果已经是叶节点 return ; int mid = l + r >> 1; //当前区间中点 build(u << 1, l, mid); //递归构建左右儿子 build(u << 1 | 1, mid + 1, r); return ; }区间查询操作
假如我们要查找区间[l,r]中的最大值，将会有以下几种情况，以[3, 7]为例；
查询区间[l, r]，以u为节点的当前树中区间为[tr[u].l, tr[u].r]
1、第一种情况树中区间是查询区间的子集，也就是全部符合。
tr[u].l >= l && tr[u].r <= r如进入u = 5时，区间[3,4]， 3 >= 3 && 4 <= 7。直接返回当前区间最大值即可，不需要在往下递归了。
2、查询区间的左端点L <= mid，我们需要去左儿子查找相应的值
if(l <= mid) //判断是否和左儿子有交集 Max = query(u << 1, l, r);3、查询区间的右端点R > mid，我们需要去右儿子查找相应的值
if(r > mid) //判断是否和右区间有交集 Max = max(Max, query(u << 1 | 1, l, r));总体代码如下：
int query(int u, int l, int r)// 查询函数[l, r]为查询区间，u为当前线段的编号 { if(tr[u].l >= l && tr[u].r <= r) //如果 查询区间 已经把当前 树中区间 包含完了 return tr[u].Max; int mid = tr[u].l + tr[u].r >> 1; //取中点 int Max = 0; // 存一下最大值 if(l <= mid) //判断是否和左儿子有交集 Max = query(u << 1, l, r); if(r > mid) //判断是否和右区间有交集 Max = max(Max, query(u << 1 | 1, l, r)); return Max; }单点修改操作
我们需要到达指定的叶节点去修改对应的值，在修改完之后，也要更新父节点的属性
当到达 tr[u].l == x && tr[u].r == x 时就是叶节点，此时进行更新
如果不时叶节点，取当前区间中点mid， x <= mid就递归去左儿子更新， x > mid 就递归去右儿子更新，更新后同时对父节点进行更新操作pushup
更新父节点操作
void pushup(int u) //由子节点信息，更新父节点信息 { tr[u].Max = max(tr[u << 1].Max, tr[u << 1 | 1].Max); }单点修改代码：
void modify(int u, int x, int c) //当前编号u,目标位置x，修改值为c { if(tr[u].l == x && tr[u].r == x) //到达叶节点，即目标位置 tr[u].Max = c; else { int mid = tr[u].l + tr[u].r >> 1; if(x <= mid) modify(u << 1, x, c); //递归去左儿子查找 else modify(u <<1 | 1, x ,c); //递归去右儿子查找 //更新后，我们需要将父节点的最大值同步更新 pushup(u); } return ; } 代码模板
代码里有详细注释
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 2e5 + 10; typedef long long ll; int n, m, p, last; //last是上一个操作的答案 struct node{ int l, r; int Max; //区间[l, r]的最大值 }tr[4 * N]; void build(int u, int l, int r)//u是当前节点位置,l、r为区间边界 { tr[u] = {l, r}; //存下当前节点左右边界 if(l == r) //如果已经是叶节点 return ; int mid = l + r >> 1; //当前区间中点 build(u << 1, l, mid); //递归构建左右儿子 build(u << 1 | 1, mid + 1, r); return ; } void pushup(int u) //由子节点信息，更新父节点信息 { tr[u].Max = max(tr[u << 1].Max, tr[u << 1 | 1].Max); } int query(int u, int l, int r)// 查询函数[l, r]为查询区间，u为当前线段的编号 { if(tr[u].l >= l && tr[u].r <= r) //如果 查询区间 已经把当前 树中区间 包含完了 return tr[u].Max; int mid = tr[u].l + tr[u].r >> 1; //取中点 int Max = 0; // 存一下最大值 if(l <= mid) //判断是否和左儿子有交集 Max = query(u << 1, l, r); if(r > mid) //判断是否和右区间有交集 Max = max(Max, query(u << 1 | 1, l, r)); return Max; } void modify(int u, int x, int c) //当前编号u,目标位置x，修改值为c { if(tr[u].l == x && tr[u].r == x) //到达叶节点，即目标位置 tr[u].Max = c; else { int mid = tr[u].l + tr[u].r >> 1; if(x <= mid) modify(u << 1, x, c); //递归去左儿子查找 else modify(u <<1 | 1, x ,c); //递归去右儿子查找 //更新后，我们需要将父节点的最大值同步更新 pushup(u); } return ; } int main() { scanf("%d %d", &m, &p); build(1, 1, m); while(m--) { char op[2]; scanf("%s", op); int x; if(op[0]=='A')//单点修改 { scanf("%d",&x); modify(1,++n,((ll)x + last)%p); } else // 区间查询 { scanf("%d",&x); last=query(1,n-x+1,n); printf("%d\n",last); } } return 0; } 1.3 区间修改，单点查询——待更新
题目描述
题目链接：
思路分析
代码模板
1.4 进阶线段树——区间修改 区间查询
题目描述
题目链接：243. 一个简单的整数问题2 – AcWing题库
思路分析
对于区间修改，如果在不添加懒标记的情况下，我们需要将与这个区间中相关的区间都要修改，我们修改的时间复杂度为O(n)，例如
我们把[1，5]都加上d，有如下图，操作次数为2 * N
此时就有懒标记应运而生，可以让我们在log(n)的时间完成操作
构建结构体时我们添加一个懒标记
struct Node{ int l, r; ll sum; //区间和 ll add; //懒标记 }tr[4 * N];懒标记add：给以当前节点为根的子树中的每一个节点加上add（add到符合条件的根节点就停止，可以有效减少修改次数）
sum：是考虑当前节点及子节点上的所有标记，当前的区间和（不考虑父节点信息）
add：给当前节点的所有儿子都加上add（不包括自己）
举例， 我们把[1，5]都加上d，只需要修改2个区间
我们并没有直接对叶节点（最后一行）进行修改，在我们对一个点进行查询的时候，需要把叶节点的父节点上的所有add懒标记都加上
例如：位置3的初始值为0，查询如下：
下面给出具体代码操作。
建树操作
建树操作都差不多，叶节点初始sum = a[r]，add = 0
void build(int u, int l, int r) { if(l == r)// 叶节点 tr[u] = {l, r, a[r], 0}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid); //递归构建左右儿子 build(u << 1 | 1, mid + 1, r); pushup(u); //更新父节点u } }更新父节点操作
根据子节点的状态，更新父节点的sum
void pushup(int u)//根据 子节点 更新 父节点 属性 { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; }更新子节点操作
父节点root，左儿子left，右儿子right
左右儿子分别加上父节点的add懒标记
left.add += root.add; right.add += root.add; 左右儿子中所有元素都要加上add，则左右儿子区间和sum要加上区间长度 * add，即
left.sum += (ll)(left.r - left.l + 1) * root.add; right.sum += (ll)(right.r - right.l + 1) * root.add; 由于懒标记已经向下传递，则父节点的懒标记就要清零
root.add = 0;// 父节点的 懒标记 清零这里有可能会有一个问题，是为什么父节点root清除懒标记时 不用更新root.sum，这是因为上面我们说过父节点的add是不包括自己的，只给自己儿子加，父节点的sum更新在给父节点添加add时就已经更新了父节点的sum，具体代码请看下下面的区间修改操作
void pushdown(int u)// 根据 父节点 更新 子节点 属性 { auto &root = tr[u]; auto &left = tr[u << 1]; auto &right = tr[u << 1 | 1]; if(root.add) //如果当前父节点 有懒标记 向下传递 { left.add += root.add; //左儿子加上父节点的add left.sum += (ll)(left.r - left.l + 1) * root.add; right.add += root.add; //有儿子加上父节点的add right.sum += (ll)(right.r - right.l + 1) * root.add; root.add = 0;// 父节点的 懒标记 清零 } }区间修改操作
当前节点代表的区间 是查询区间的子区间时，直接加上add，并且更新sum,
举例给[1,5]加上d
void modify(int u, int l, int r, int d)//区间修改 把[L, R]区间 +d { if(tr[u].l >= l && tr[u].r <= r)// 当前区间为目标区间的子区间 { tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * d;// 更新区间和, +区间长度 * d tr[u].add += d; //更新懒标记 } else //一定要分裂，此时目标区间不能代表整个区间，分裂寻找满足子区间再添加 { pushdown(u); //分裂就要下放懒标记 int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u << 1, l, r, d); if(r > mid) modify(u << 1 | 1, l, r, d); pushup(u); //修改完再更新 父节点 状态 } }区间查询操作
由于我们要对区间进行查询，所以与查询区间有交集的节点都要把懒标记向下传递清零，否则查询就会有问题，递归进行查询
ll query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r)// 当前区间是查询区间的子区间 return tr[u].sum; pushdown(u); //清一下懒标记 int mid = tr[u].l + tr[u].r >> 1; ll sum = 0; if(l <= mid) //与左儿子有交集 sum += query(u << 1, l, r); if(r > mid) //与右儿子有交集 sum += query(u << 1 | 1, l, r); return sum; }代码模板
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10; typedef long long ll; int n, m; int a[N]; struct Node{ int l, r; ll sum; //区间和 ll add; //懒标记 }tr[4 * N]; void pushup(int u)//根据 子节点 更新 父节点 属性 { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void pushdown(int u)// 根据 父节点 更新 子节点 属性 { auto &root = tr[u]; auto &left = tr[u << 1]; auto &right = tr[u << 1 | 1]; if(root.add) //如果当前父节点 有懒标记 向下传递 { left.add += root.add; left.sum += (ll)(left.r - left.l + 1) * root.add; right.add += root.add; right.sum += (ll)(right.r - right.l + 1) * root.add; root.add = 0;// 父节点的 懒标记 清零 } } void build(int u, int l, int r) { if(l == r)// 叶节点 tr[u] = {l, r, a[r], 0}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid); //递归构建左右儿子 build(u << 1 | 1, mid + 1, r); pushup(u); //更新父节点u } } void modify(int u, int l, int r, int d)//区间修改 把[L, R]区间 +d { if(tr[u].l >= l && tr[u].r <= r)// 当前区间为目标区间的子区间 { tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * d;// 更新区间和, +区间长度 * d tr[u].add += d; //更新懒标记 } else //一定要分裂，此时目标区间不能代表整个区间，分裂寻找满足子区间再添加 { pushdown(u); //分裂就要下放懒标记 int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u << 1, l, r, d); if(r > mid) modify(u << 1 | 1, l, r, d); pushup(u); //修改完再更新 父节点 状态 } } ll query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r)// 当前区间是查询区间的子区间 return tr[u].sum; pushdown(u); //清一下懒标记 int mid = tr[u].l + tr[u].r >> 1; ll sum = 0; if(l <= mid) //与左儿子有交集 sum += query(u << 1, l, r); if(r > mid) //与右儿子有交集 sum += query(u << 1 | 1, l, r); return sum; } int main() { scanf("%d %d",&n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, 1, n); char op[2]; int l, r, d; while(m--) { scanf("%s %d %d", op, &l, &r); if(op[0] == 'C') //区间修改 { scanf("%d", &d); modify(1, l, r, d); } else printf("%lld\n", query(1, l, r)); } return 0; } 1.5 乘法线段树——区间修改 区间查询
题目描述
题目链接：1277. 维护序列 – AcWing题库
思路分析
由于既有乘法又有加法，乘法与加法的先后修改顺序也会影响最后的结果
我们需要开2个懒标记，一个是存加法，一个存乘法
结构体定义如下：
struct Node{ int l, r; int sum; //区间和 int add; // 加法懒标记 int mul; // 乘法懒标记 }tr[4 *N];建树操作
与正常线段树没什么不同，就是注意乘法懒标记初始化为1
void build(int u, int l, int r) { if(l == r) tr[u] = {l, r, a[r], 0, 1};// 乘法懒标记初始化为1 else { tr[u] = {l, r, 0, 0, 1}; //这里sum先为0 后面会更新 int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } }更新父节点操作
根据左右儿子更新父节点的和sum，% p是题目要求
void pushup(int u) //由 子节点 更新 父节点 的属性 { tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p; }更新子节点操作
我们有2种懒标记需要传递，做法是先乘后加
在传递懒标记时，我们需要对子节点的sum进行更新，但是加法和乘法我们并不知道先后顺序，得到的结果也不同，这里的做法就是先乘后加
以下列举情况并证明，可以看着下面的代码来验证
先乘后加 说的是对sum的更新，mul直接更新即可
void eval(Node &t, int add, int mul) { t.sum = ((ll)t.sum * mul + (ll)add * (t.r - t.l + 1)) % p;// 先乘再加 t.mul = (ll)t.mul * mul % p; t.add = ((ll)t.add * mul + add) % p; }（1）2个加法，mul = 1， add = a + b
sum = sum * mul + add * (r - l + 1) ;（2）2个乘法，mul = a * b, add = 0，直接更新即可
sum = sum * mul;（3）先乘后加，mul = a, add = b，也是直接更新即可
sum = sum * mul + add * (r - l + 1);（4）先加后乘，可以这样理解，此时mul = b， add = a * b
sum = sum * mul + add * (r - l + 1); add = add * mul + add;void eval(Node &t, int add, int mul) // { t.sum = ((ll)t.sum * mul + (ll)add * (t.r - t.l + 1)) % p;// 先乘再加 t.mul = (ll)t.mul * mul % p; t.add = ((ll)t.add * mul + add) % p; } void pushdown(int u)// 传递懒标记 { eval(tr[u << 1], tr[u].add, tr[u].mul); //传递懒标记到左右儿子 eval(tr[u << 1 | 1], tr[u].add, tr[u].mul); tr[u].add = 0; //清空懒标记 tr[u].mul = 1; }区间修改操作
void modify(int u, int l, int r, int add, int mul)// 区间修改 { if(tr[u].l >= l && tr[u].r <= r) eval(tr[u], add, mul); else { pushdown(u); //传递懒标记 同时清空懒标记 int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) //与左儿子有交集 modify(u << 1, l, r, add, mul); if(r > mid) //与右儿子有交集 modify(u << 1 | 1, l, r, add, mul); pushup(u); } }区间查询操作
int query(int u, int l, int r) //区间查询 { if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum; pushdown(u); //清除一下懒标记 int sum = 0; int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) sum = query(u << 1, l, r); if(r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p; return sum; }代码模板
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10; typedef long long ll; int n, m, p; int a[N]; struct Node{ int l, r; int sum; //区间和 int add; // 加法懒标记 int mul; // 乘法懒标记 }tr[4 *N]; void pushup(int u) //由 子节点 更新 父节点 的属性 { tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p; } void eval(Node &t, int add, int mul) // { t.sum = ((ll)t.sum * mul + (ll)add * (t.r - t.l + 1)) % p;// 先乘再加 t.mul = (ll)t.mul * mul % p; t.add = ((ll)t.add * mul + add) % p; } void pushdown(int u)// 传递懒标记 { eval(tr[u << 1], tr[u].add, tr[u].mul); //传递懒标记到左右儿子 eval(tr[u << 1 | 1], tr[u].add, tr[u].mul); tr[u].add = 0; //清空懒标记 tr[u].mul = 1; } void build(int u, int l, int r) { if(l == r) tr[u] = {l, r, a[r], 0, 1};// 乘法懒标记初始化为1 else { tr[u] = {l, r, 0, 0, 1}; //这里sum先为0 后面会更新 int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } } void modify(int u, int l, int r, int add, int mul)// 区间修改 { if(tr[u].l >= l && tr[u].r <= r) eval(tr[u], add, mul); else { pushdown(u); //传递懒标记 同时清空懒标记 int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) //与左儿子有交集 modify(u << 1, l, r, add, mul); if(r > mid) //与右儿子有交集 modify(u << 1 | 1, l, r, add, mul); pushup(u); } } int query(int u, int l, int r) //区间查询 { if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum; pushdown(u); //清除一下懒标记 int sum = 0; int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) sum = query(u << 1, l, r); if(r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p; return sum; } int main() { scanf("%d %d", &n, &p); for(int i = 1 ; i <= n; i++) scanf("%d",&a[i]); build(1, 1, n);// 建树 int op, l, r, d; scanf("%d", &m); while(m--) { scanf("%d %d %d", &op, &l, &r); if(op == 1) //乘法 { scanf("%d", &d); modify(1, l, r, 0, d); } else if(op == 2)// 加法 { scanf("%d", &d); modify(1, l, r, d, 1); } else// 区间查询 printf("%d\n",query(1, l, r)); } return 0; }二、题目练习
2.1 区间查询，单点修改
2.1.1 板子题 区间和 + 单点修改
题目描述
题目链接：P2068 统计和 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路分析
代码模板
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10; typedef long long ll; int n, m; struct{ int l, r; ll sum; }tr[4 * N]; 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, r, 0}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } } void modify(int u, int x, int c) { if(tr[u].l == x && tr[u].r == x) tr[u].sum += c; else { int mid = tr[u].l + tr[u].r >> 1; if(x <= mid) modify(u << 1, x, c); else modify(u << 1 | 1, x, c); pushup(u); } } ll query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum; ll sum = 0; int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) sum = query(u << 1, l, r); if(r > mid) sum += query(u << 1 | 1, l, r); return sum; } int main() { scanf("%d %d",&n, &m); build(1, 1, n); while(m--) { char op[2]; int x, y; scanf("%s %d %d", op, &x, &y); if(op[0] == 'x') modify(1, x, y); else printf("%lld\n", query(1, x, y)); } return 0; }2.1.2 最大连续子段和
题目描述
题目链接：245. 你能回答这些问题吗 – AcWing题库
思路分析
代码模板
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 5e5 + 10; struct Node{ int l, r; int tmax; //最大连续子段和 int lmax, rmax; //最大前缀和 最大后缀和 int sum; //区间和 }tr[4 * N]; int n, m; int a[N]; //存原数 void pushup(Node &u, Node &l, Node &r) // { u.sum = l.sum + r.sum; //区间和 = 左右儿子区间和 //最大连续子段和 =(取最大) 左儿子最大连续 右儿子最大连续 左儿子最大后缀 + 右儿子最大前缀 u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax); u.lmax = max(l.lmax, l.sum + r.lmax); //左儿子最大前缀 左儿子区间和 + 右儿子最大前缀 u.rmax = max(r.rmax, r.sum + l.rmax); //右儿子最大后缀 右儿子区间和 + 左儿子最大后缀 } void pushup(int u)//由 子节点 更新 父节点的属性,u是父节点 { pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); } void build(int u, int l, int r)// 建树 { if(l == r) //到达叶节点 tr[u] = {l, r, a[r], a[r], a[r], a[r]}; else { tr[u] = {l, r}; //更新左右端点 int mid = l + r >> 1; build(u << 1, l, mid); //递归建立左右儿子 build(u << 1 | 1, mid + 1, r); pushup(u); //由于儿子的数据更新了，所以当前父节点u的属性也要更新 } } void modify(int u, int x,int c)//当前区间编号位为u, 将位置x的值改为c { if(tr[u].l == x && tr[u].r == x) //已经到达叶节点 tr[u] = {x, x, c, c, c, c}; //更新节点 else { int mid = tr[u].l + tr[u].r >> 1; if(x <= mid) // 目标位置在左儿子中 modify(u << 1, x, c); else //目标位置在右儿子中 modify(u << 1 | 1, x, c); pushup(u); //由于儿子的数据更新了，所以当前父节点u的属性也要更新 } } Node query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r)//树中区间是查询区间的子集 return tr[u]; else { int mid = tr[u].l + tr[u].r >> 1; if(r <= mid) //查询区间全部在左儿子中 return query(u << 1, l, r); else if(l > mid) //查询区间全部在右儿子中 return query(u << 1 | 1, l, r); else //如果横跨2个区间 { //我们需要根据左右儿子提供的信息来更新目标区间的属性 //这个更新结果不会更新树上节点的内容， 返回到res了 auto left = query(u << 1, l, r); auto right = query(u << 1 | 1, l, r); Node res; pushup(res, left, right); return res; } } } int main() { scanf("%d %d",&n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, 1, n); while(m--) { int k, x, y; scanf("%d %d %d", &k, &x, &y); if(k == 1) // 区间查询 { if(x > y) swap(x, y); printf("%d\n", query(1, x, y).tmax); } else //单点更新 modify(1, x, y); } return 0; }
2.1.3 区间查询+最小值
题目描述
题目链接：P1816 忠诚 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路分析
只有区间查询没有修改操作，不用写modify，线段树维护区间最小值即可
代码模板
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10; int n, m; int a[N]; struct Node{ int l, r; int Min; }tr[4 * N]; void pushup(int u) { tr[u].Min = min(tr[u << 1].Min, tr[u << 1 | 1].Min); } void build(int u, int l, int r) { if(l == r) tr[u] = {l, r, a[r]}; else { tr[u] = {l, 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(tr[u].l >= l && tr[u].r <= r) return tr[u].Min; int res = 1e9; int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) res = min(res, query(u << 1, l, r)); if(r > mid) res = min(res, query(u << 1 | 1, l, r)); return res; } int main() { scanf("%d %d",&n, &m); for(int i = 1; i <= n; i++) scanf("%d",&a[i]); build(1, 1, n); while(m--) { int l, r; scanf("%d %d", &l, &r); printf("%d ",query(1, l, r)); } return 0; }免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/126666.html
