线段树
线段树的概念
线段树是一种用于区间处理的数据结构，用二叉树来构造
线段树是二叉树，一个区间每次被折一半往下分，所有最多分次就能找到。这就是线段树效率高的原因，使用了二叉树折半查找的方法。
线段树的基本操作
单点修改，区间查询
【max】给定一个n（n <= 100000）个元素的数组A，有m（m <= 100000）个操作，共两种操作：
- 单点修改：（C a c）表示将第a个元素变成c；
- 区间查询：（Q a b）表示询问区间[a, b]的最大值；
const int maxn = 2e5+1;
int p[maxn];
struct node {
int l, r, val;
node () {}
node (int l, int r, int val): l(l), r(r), val(val){}
node operator+ (const node n1) { // 区间合并 -- 求最值
return node(l, n1.r, max(val, n1.val));
}
}pos[maxn << 2];
void BuildTree(int root, int l, int r) { // 建树
if (l == r) {
pos[root] = node(l, r, p[l]);
return ;
}
int mid = l + r >> 1;
BuildTree(root<<1, l, mid);
BuildTree(root<<1|1, mid + 1, r);
pos[root] = pos[root<<1] + pos[root<<1|1];
}
void UpData(int root, int l, int r, int u, int val) { // 单点修改
if (l == r) {
pos[root].val = val;
return ;
}
int mid = l + r >> 1;
if (mid >= u) UpData(root<<1, l, mid, u, val);
else if (mid < u) UpData(root<<1|1, mid+1, r, u, val);
pos[root] = pos[root<<1] + pos[root<<1|1];
}
node Query(int root, int l, int r, int ql, int qr) { // 区间查询
if (l == ql && r == qr) return pos[root];
int mid = l + r >> 1;
if (mid >= qr) return Query(root<<1, l, mid, ql, qr);
if (mid < ql) return Query(root<<1|1, mid+1, r, ql, qr);
return Query(root<<1, l, mid, ql, mid) + Query(root<<1|1, mid+1, r, mid+1, qr);
}区间修改，区间查询 —— 懒惰标记
【sum】给定一个n（n <= 100000）个元素的数组A，有m（m <= 100000）个操作，共两种操作：
- 区间修改：（A a b c）表示将区间[a, b]的每个元素加上一个值c；
- 区间查询：（Q a b）表示询问区间[a, b]的元素和；
const int maxn = 2e5+1;
int p[maxn];
struct node {
int l, r;
long long val, lazy;
node () {lazy = 0;}
node (int l, int r, long long val): l(l), r(r), val(val){lazy = 0;}
node operator+ (const node n1) { // 区间合并 -- 求和
return node(l, n1.r, val + n1.val);
}
}pos[maxn << 2];
void BuildTree(int root, int l, int r) { // 建树
if (l == r) {
pos[root] = node(l, r, p[l]);
return ;
}
pos[root].lazy = 0; // 清空懒惰标记
int mid = l + r >> 1;
BuildTree(root<<1, l, mid);
BuildTree(root<<1|1, mid + 1, r);
pos[root] = pos[root<<1] + pos[root<<1|1];
}
void PushDown(int root) { // 懒惰更新
if (pos[root].lazy) {
pos[root<<1].val += pos[root].lazy*(pos[root<<1].r-pos[root<<1].l+1);
pos[root<<1].lazy += pos[root].lazy;
pos[root<<1|1].val += pos[root].lazy*(pos[root<<1|1].r-pos[root<<1|1].l+1);
pos[root<<1|1].lazy += pos[root].lazy;
pos[root].lazy = 0;
}
}
void UpData(int root, int l, int r, int ul, int ur, int val) { // 区间更新
if (l == ul && r == ur) {
pos[root].val += val*(r-l+1);
pos[root].lazy += val;
return ;
}
PushDown(root);
int mid = l + r >> 1;
if (mid >= ur) UpData(root<<1, l, mid, ul, ur, val);
else if (mid < ul) UpData(root<<1|1, mid+1, r, ul, ur, val);
else {
UpData(root<<1, l, mid, ul, mid, val);
UpData(root<<1|1, mid+1, r, mid+1, ur, val);
}
pos[root] = pos[root<<1] + pos[root<<1|1];
}
node Query(int root, int l, int r, int ql, int qr) { // 区间查询
if (l == ql && r == qr) return pos[root];
PushDown(root);
int mid = l + r >> 1;
if (mid >= qr) return Query(root<<1, l, mid, ql, qr);
if (mid < ql) return Query(root<<1|1, mid+1, r, ql, qr);
return Query(root<<1, l, mid, ql, mid) + Query(root<<1|1, mid+1, r, mid+1, qr);
}
/*
int Query(int root, int l, int r, int q) { // 单点查询
if (l == r) return pos[root].val;
PushDown(root);
int mid = l + r >> 1;
if (mid >= q) return Query(root<<1, l, mid, q);
return Query(root<<1|1, mid+1, r, q);
}
*/
线段树拓展
1. 不连续区间修改，单点查询 —— 分组线段树
【p[x]】给定一个n（n <= 50000）个元素的数组P，有m（m <= 50000）个操作，共两种操作：
- 不连续区间修改：（A a b k c）表示将区间[a, b]中满足(i-a)%k == 0 的元素加上一个值c；（其中k<=10）
- 单点查询：（Q a b）表示询问区间[a, b]的元素和；
注： 建k*(k+1)/2棵树，每次修改只对一棵树进行修改，每次查询要对所有有效树都进行一次查询。
#include<cstdio>
using namespace std;
const int maxn = 5e4+1;
int p[maxn], d[] = {0,0,1,3,6,10,15,21,28,36,45};
int pos[maxn<<2][55]; // 单点查询-线段树
void BuildTree(int root, int l, int r, int rt) { // 建树
pos[root][rt] = 0;
if (l == r) return ;
int mid = (l + r) >> 1;
BuildTree(root<<1, l, mid, rt);
BuildTree(root<<1|1, mid + 1, r, rt);
}
void PushDown(int root, int rt) { // 最·懒惰更新
if (pos[root][rt]) {
pos[root<<1][rt] += pos[root][rt];
pos[root<<1|1][rt] += pos[root][rt];
pos[root][rt] = 0;
}
}
void UpData(int root, int l, int r, int ul, int ur, int val, int rt) { // 区间修改
if (l == ul && r == ur) {
pos[root][rt] += val;
return ;
}
PushDown(root, rt);
int mid = l + r >> 1;
if (mid >= ur) UpData(root<<1, l, mid, ul, ur, val, rt);
else if (mid < ul) UpData(root<<1|1, mid+1, r, ul, ur, val, rt);
else {
UpData(root<<1, l, mid, ul, mid, val, rt);
UpData(root<<1|1, mid+1, r, mid+1, ur, val, rt);
}
}
int Query(int root, int l, int r, int q, int rt) { // 单点查询
if (l == r) return pos[root][rt];
PushDown(root, rt);
int mid = l + r >> 1;
if (mid >= q) return Query(root<<1, l, mid, q, rt);
return Query(root<<1|1, mid+1, r, q, rt);
}
int main() {
int n; while(scanf("%d", &n) != EOF) {
for(int i = 0; i < 55; ++ i) { // 建55课线段树
BuildTree(1, 1, n, i);
}
for(int i = 1; i <= n; ++ i) {
scanf("%d", &p[i]);
}
int m; scanf("%d", &m);
while(m --) {
int op; scanf("%d", &op);
if (op == 1) {
int a, b, k, c; scanf("%d%d%d%d", &a, &b, &k, &c);
UpData(1, 1, n, a, b, c, d[k]+a%k);
}
else {
int x, res = 0; scanf("%d", &x);
for(int i = 1; i <= 10; ++ i) {
res += Query(1, 1, n, x, d[i]+x%i);
}
printf("%d\n", res + p[x]);
}
}
}
return 0;
}
2. 离散化
sort(g + 1, g + n + 1); // 排序
m = unique(g+1, g+1+n) - (g+1); // 去重
for(int i = 1; i <= n; ++ i) {
p[i] = lower_bound(g+1, g+m+1, p[i]) - g;
}3. RMQ 问题
RMQ（Range Minimum/Maximum Query），即区间最值查询。ST表（Tarjan的Sparse-Table算法） 求解 RMQ 一般用较长时间做预处理init(n)，时间复杂度为O(nlogn)，然后可以在O(1)的时间内处理每次查询RMQ(l,r)。
const int maxn = 1e6+1;
int a[maxn];
int d[maxn][32]; // 从第i个数起连续2^j个数中的最小值
int init(int n) { // 预处理
for(int i = 1; i <= n; ++ i) {
d[i][0] = a[i];
}
for(int i = n; i >= 1; -- i) {
for(int j = 1; i + (1<<j-1) <= n; ++ j) {
d[i][j] = min(d[i][j-1], d[i+(1<<j-1)][j-1]);
}
}
}
int RMQ(int l, int r) {
int k = 31 - __builtin_clz(r-l+1);
return min(d[l][k], d[r-(1<<k)+1][k]);
}
查看19道真题和解析
