主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
线段树
最后更新于 2025-07-31 11:51:29
作者
niuqichongtian
分类
算法·理论
复制 Markdown
查看原文
删除文章
更新内容
# 线段树 ## 线段树简述 > ### 线段树是数据结构中的常用算法,常用于解决序列修改与查询问题 > by OI wiki > > > 线段树的思路在于,将数组 $a[]$ 分为一个树\ > > 这个树就是线段树\ > > 本质是将数组中 $[1, N]$ 分为 $\displaystyle {[1, \frac{N}{2}] }$ 和 $\displaystyle {[\frac{N}{2}+1, N] }$\ > > 以此类推,向下分治\ > > 则每次对一个区间修改时间复杂度为 $\displaystyle{ O(NlogN) }$\ > > 如何将其变为 $O(logN)$ 呢?设 $lazy_tag$ > > > ### $lazy\_tag 延迟标记$ > > > > > > 延迟标记的意义在于,鉴于 $pushdown$ 操作时间复杂度是 $O(1)$ 的,辣么我们oier的聪明材质有用处了\ > > > 辣么怎么省时间呢?其实我们也有一些必须递归的时候对扒?我们把应该递归的东西记录,之后就可以看:如果经过这里时,必须要继续递归下去了,则我们此时可以同步 $lazy\_tag$ \ > > > 同步它的意义是啥?其实就是保证下面节点权重(区间和或最大值,总之是询问的答案(或间接的))的正确性。则若递归时不去更新,则正确性无法保证 --- ## 习题集 ###### 例题 1. [加法和查询](https://www.luogu.com.cn/problem/P3372) 2. [加乘和查询](https://www.luogu.com.cn/problem/P3373) ###### 习题 1. [忠诚](https://www.luogu.com.cn/problem/P1816) 2. [方差](https://www.luogu.com.cn/problem/P1471) 3. [STEP](https://www.luogu.com.cn/problem/P6492) 4. [三元上升子序列](https://www.luogu.com.cn/problem/P1637) 5. [色板游戏](https://www.luogu.com.cn/problem/P1558) 6. [棠梨煎雪](https://www.luogu.com.cn/problem/P5522) 7. [上帝造题的七分钟 $2$ / 花神游历各国](https://www.luogu.com.cn/problem/P4145) 8. [序列操作](https://www.luogu.com.cn/problem/P2572) 9. [Points](https://www.luogu.com.cn/problem/CF19D) --- ## 模板题code ```cpp // P3372 record 188117140 #include <bits/stdc++.h> #define I using #define AK namespace #define IOI std; #define int long long #undef INT_MIN #define INT_MIN (LONG_LONG_MIN + 1145) #undef INT_MAX #define INT_MAX (LONG_LONG_MAX - 1145) #define P1 "±ê¼Çµã1" #define P2 "±ê¼Çµã2" #define P3 "±ê¼Çµã3" #define P4 "±ê¼Çµã4" #define P5 "±ê¼Çµã5" #define P6 "±ê¼Çµã6" #define P7 "±ê¼Çµã7" #define P8 "±ê¼Çµã8" #define P9 "±ê¼Çµã9" #define P0 "±ê¼Çµã0" I AK IOI; namespace CSP { inline void read(int &x) { x = 0; char c = getchar(); int pn = 1; while (!isdigit(c)) { if (c == '-') pn = -1; c = getchar(); } while (isdigit(c)) { x = x * 10 + c - 48; c = getchar(); } x *= pn; return; } inline void write(int x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) write(x / 10); putchar(x % 10 + 48); return; } struct inputstream { inputstream operator>>(int &x) { read(x); return *this; } } in; struct outputstream { outputstream operator<<(int x) { if (x == INT_MIN) { putchar('-'); putchar('2'); putchar('1'); putchar('4'); putchar('7'); putchar('4'); putchar('8'); putchar('3'); putchar('6'); putchar('4'); putchar('8'); } else write(x); putchar('\n'); return *this; } } out; } I AK CSP; int N, Q; int a[114514]; int t[414514]; int lzy[414514]; namespace Segmental_Tree { /* TODO (niuqichongtian #1#): | ¡Ì 1. inline bool in_range(int L, int R, int l, int r) | ¡Ì 2. inline bool out_range(int L, int R, int l, int r) | ¡Ì 3. inline void pushup(int u) | ¡Ì 4. inline void maketag(int u, int len, int k) | ¡Ì 5. inline void pushdown(int u, int L, int R) | ¡Ì 6. inline void build(int u, int l, int r) | ¡Ì 7. inline void update(int u, int L, int R, int l, int r, int k) | ¡Ì 8. inline int query(int u, int L, int R, int l, int r) | ¡Ì */ inline bool in_range(int L, int R, int l, int r) { if (l <= L && R <= r) return true; return false; } inline bool out_range(int L, int R, int l, int r) { if (R < l || r < L) return true; return false; } inline void pushup(int u) { t[u] = t[u * 2] + t[u * 2 + 1]; return; } inline void maketag(int u, int len, int k) { lzy[u] += k; t[u] += len * k; return; } inline void pushdown(int u, int L, int R) { int M = L + R >> 1; maketag(u * 2, M - L + 1, lzy[u]); maketag(u * 2 + 1, R - (M + 1) + 1, lzy[u]); lzy[u] = 0; return; } inline void build(int u, int l, int r) { if (l == r) { t[u] = a[l]; return; } int m = l + r >> 1; build(u * 2, l, m); build(u * 2 + 1, m + 1, r); pushup(u); return; } inline void update(int u, int L, int R, int l, int r, int k) { if (in_range(L, R, l, r)) maketag(u, R - L + 1, k); else if (!out_range(L, R, l, r)) { int M = L + R >> 1; pushdown(u, L, R); update(u * 2, L, M, l, r, k); update(u * 2 + 1, M + 1, R, l, r, k); pushup(u); } return; } inline int query(int u, int L, int R, int l, int r) { if (in_range(L, R, l, r)) return t[u]; else if (out_range(L, R, l, r)) return 0; else { // a part of the range we want to find is in [L, R] int M = L + R >> 1; pushdown(u, L, R); return query(u * 2, L, M, l, r) + query(u * 2 + 1, M + 1, R, l, r); } } } I AK Segmental_Tree; signed main(signed argc, char const *argv[]) { in >> N >> Q; for (register int i = 1; i <= N; i++) in >> a[i]; build(1, 1, N); int x, y, k; int op; while (Q--) { in >> op >> x >> y; if (op == 1) { in >> k; update(1, 1, N, x, y, k); } else out << query(1, 1, N, x, y); // for (int i = 1; i <= N; i++) // cout << query(1, 1, N, i, i) << " "; // putchar('\n'); } return 0; } ``` --- ```cpp // P3373 record 188306664 #include <bits/stdc++.h> #define I using #define AK namespace #define IOI std #define int long long #undef INT_MIN #define INT_MIN (LONG_LONG_MIN + 1145) #undef INT_MAX #define INT_MAX (LONG_LONG_MAX - 1145) #define P1 "标记点1" #define P2 "标记点2" #define P3 "标记点3" #define P4 "标记点4" #define P5 "标记点5" #define P6 "标记点6" #define P7 "标记点7" #define P8 "标记点8" #define P9 "标记点9" #define P0 "标记点0" I AK IOI; AK CSP { inline void read(int &x) { x = 0; char c = getchar(); int pn = 1; while (!isdigit(c)) { if (c == '-') pn = -1; c = getchar(); } while (isdigit(c)) { x = x * 10 + c - 48; c = getchar(); } x *= pn; return; } inline void write(int x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) write(x / 10); putchar(x % 10 + 48); return; } struct inputstream { inputstream operator>>(int &x) { read(x); return *this; } } in; struct outputstream { void operator<<(int x) { write(x); putchar('\n'); return; } } out; } I AK CSP; // 快读快写 int N, Q, mod; int a[100007]; // 原数组 int t[400007]; // 线段树区间和 int lzy_mul[400007]; // 乘法延迟标记(懒标记lazy_tag) int lzy_add[400007]; // 加法延迟标记 AK Segment_Tree { // 线段树子函数集合 /* function list :+--------------------------------------------------------------+ | inline bool in_range(int L, int R, int l, int r) | | inline bool out_range(int L, int R, int l, int r) | | inline void makeaddtag(int u, int L, int R, int c) | | inline void makemultag(int u, int L, int R, int c) | | inline void pushdown(int u, int L, int R) | | inline void pushup(int u) | | inline void build(int u, int L, int R) | | inline void updadd(int u, int L, int R, int l, int r, int c) | | inline void updmul(int u, int L, int R, int l, int r, int c) | | inline int query(int u, int L, int R, int l, int r) | +--------------------------------------------------------------+ 函数名应该不难读懂^_^ */ inline bool in_range(int L, int R, int l, int r) { if (l <= L && R <= r) return true; // 整体l <= L <= R <= r return false; // 可能有交集, 但不被包含 } inline bool out_range(int L, int R, int l, int r) { if (R < l || r < L) return true; // 完全无交 return false; // 有交集 } inline void makeaddtag(int u, int L, int R, int c) { lzy_add[u] = (lzy_add[u] + c) % mod; t[u] = (t[u] + (R - L + 1) * c) % mod; // 取模!!! return; } inline void makemultag(int u, int L, int R, int c) { lzy_mul[u] = (lzy_mul[u] * c) % mod; lzy_add[u] = (lzy_add[u] * c) % mod; t[u] = (t[u] * c) % mod; // 取模!!! return; } inline void pushdown(int u, int L, int R) { int M = L + R >> 1; // 无需加括号(问题自己百度) register int ls = u << 1; register int rs = u << 1 | 1; // 前项是偶数, 不用担心1|1 register int ll = M - L + 1; register int rl = R - (M + 1) + 1; t[ls] = ( t[ls]*lzy_mul[u] + lzy_add[u]*ll ) % mod; lzy_mul[ls] = ( lzy_mul[ls] * lzy_mul[u] ) % mod; lzy_add[ls] = ( lzy_add[ls] * lzy_mul[u] + lzy_add[u] ) % mod; t[rs] = ( t[rs]*lzy_mul[u] + lzy_add[u]*rl ) % mod; lzy_mul[rs] = ( lzy_mul[rs] * lzy_mul[u] ) % mod; lzy_add[rs] = ( lzy_add[rs] * lzy_mul[u] + lzy_add[u] ) % mod; lzy_add[u] = 0; lzy_mul[u] = 1; return; } inline void pushup(int u) { t[u] = ( t[u << 1] + t[u << 1 | 1] ) % mod; return; } inline void build(int u, int L, int R) { lzy_mul[u] = 1; lzy_add[u] = 0; if (L == R) { t[u] = a[L]; // printf("t[%d] [%d, %d] = %d because it is a leaf!\n", u, L, R, t[u]); } else if (L > R) return; else { int M = L + R >> 1; build(u << 1, L, M); build(u << 1 | 1, M + 1, R); t[u] = ( t[u << 1] + t[u << 1 | 1] ); // printf("t[%d] [%d, %d] = %d because it has two sons!\n", u, L, R, t[u]); } return; } inline void updadd(int u, int L, int R, int l, int r, int c) { if (in_range(L, R, l, r)) makeaddtag(u, L, R, c); else if (!out_range(L, R, l, r)) { int M = L + R >> 1; pushdown(u, L, R); updadd(u << 1, L, M, l, r, c); updadd(u << 1 | 1, M + 1 , R, l, r, c); pushup(u); } return; } inline void updmul(int u, int L, int R, int l, int r, int c) { // printf("%d[%d, %d] finding range[%d, %d] wanting to multiply with %d is ", u, L, R, l, r, c); if (in_range(L, R, l, r)) { // cout << "in range\n"; makemultag(u, L, R, c); } else if (!out_range(L, R, l, r)) { // cout << "has intersection\n"; int M = L + R >> 1; pushdown(u, L, R); updmul(u << 1, L, M, l, r, c); updmul(u << 1 | 1, M + 1 , R, l, r, c); pushup(u); } // else cout << "out of range\n"; return; } inline int query(int u, int L, int R, int l, int r) { if (in_range(L, R, l, r)) return t[u]; else if (out_range(L, R, l, r)) return 0; else { int M = L + R >> 1; pushdown(u, L, R); // printf("%d[%d, %d] has an intersection with [%d, %d], so we go down\n", u, L, R, l, r); return ( query(u << 1, L, M, l, r) + query(u << 1 | 1, M + 1, R, l, r) ) % mod; } } } I AK Segment_Tree; signed main(signed argc, char const *argv[]) { in >> N >> Q >> mod; // 厉害吧(^v^) for (register int i = 1; i <= N; i++) in >> a[i]; build(1, 1, N); // 建树 // out << query(1, 1, N, 1, 4); /* TODO (niuqichongtian#1#): 建树有问题 12/11/24 15:42 */ int op, l, r, c; while (Q--) { in >> op; if (op == 2) { in >> l >> r >> c; updadd(1, 1, N, l, r, c); // 加法操作(op == 2) } else if (op == 1) { in >> l >> r >> c; updmul(1, 1, N, l, r, c); // 乘法操作(op == 1) } else if (op == 3) { in >> l >> r; out << query(1, 1, N, l, r); // 自动换行(op == 3) } } return 0; } ```
正在渲染内容...
点赞
0
收藏
0