线段树的区间操作与查询机制
在线段树中，区间操作主要涉及两种核心机制：向上更新（pushup）和向下传递（pushdown）。这些操作在处理区间查询和更新时至关重要。
向上更新（Pushup）
当子节点的数据发生变化时，需要通过pushup操作更新父节点。这种操作通常在构建树、修改节点值或查询结果时使用。与简单返回节点值不同，pushup可能需要结合左右子节点的信息进行复杂计算。
向下传递（Pushdown）
当父节点的值发生变化时，需要通过pushdown操作将修改传递给子节点。这种操作通常在处理延迟更新时使用，确保子节点在后续操作中能够正确反映父节点的修改。
区间最大连续和查询
为了实现区间最大连续和查询，线段树的每个节点需要维护以下信息：
lmax：左子区间最大连续和rmax：右子区间最大连续和tmax：当前区间最大连续和sum：区间总和
通过结合左右子节点的信息，可以计算出当前节点的最大连续和。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500010;
int n, m;
int w[N];
struct Node {
int l, r;
int total, leftMax, rightMax, maxSum;
} tree[N * 4];
void merge(Node &parent, Node &left, Node &right) {
parent.total = left.total + right.total;
parent.leftMax = max(left.leftMax, left.total + right.leftMax);
parent.rightMax = max(right.rightMax, right.total + left.rightMax);
parent.maxSum = max(left.maxSum, right.maxSum, left.rightMax + right.leftMax);
}
void pushUp(int index) {
merge(tree[index], tree[index << 1], tree[index << 1 | 1]);
}
void build(int index, int l, int r) {
tree[index] = {l, r};
if (l == r) {
tree[index].total = w[r];
tree[index].leftMax = tree[index].rightMax = tree[index].maxSum = w[r];
return;
}
int mid = l + r >> 1;
build(index << 1, l, mid);
build(index << 1 | 1, mid + 1, r);
pushUp(index);
}
// 其余代码省略...
区间最大公约数查询
通过构建差分数组并维护最大公约数，可以实现区间最大公约数查询。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 500010;
int n, m;
LL w[N];
struct Node {
int l, r;
LL diff, gcdVal;
} tree[N * 4];
LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
void merge(Node &parent, Node &left, Node &right) {
parent.diff = left.diff + right.diff;
parent.gcdVal = gcd(left.gcdVal, right.gcdVal);
}
void pushUp(int index) {
merge(tree[index], tree[index << 1], tree[index << 1 | 1]);
}
void build(int index, int l, int r) {
if (l == r) {
LL diff = w[r] - w[r - 1];
tree[index] = {l, r, diff, diff};
} else {
tree[index].l = l;
tree[index].r = r;
int mid = l + r >> 1;
build(index << 1, l, mid);
build(index << 1 | 1, mid + 1, r);
pushUp(index);
}
}
// 其余代码省略...
区间修改与懒标记
为了支持高效的区间修改，线段树需要支持懒标记传播。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 100010;
int n, m;
int w[N];
struct Node {
int l, r;
LL total;
LL add;
} tree[N * 4];
void pushDown(int index) {
if (tree[index].add != 0) {
int left = index << 1;
int right = index << 1 | 1;
tree[left].add += tree[index].add;
tree[left].total += (tree[left].r - tree[left].l + 1) * tree[index].add;
tree[right].add += tree[index].add;
tree[right].total += (tree[right].r - tree[right].l + 1) * tree[index].add;
tree[index].add = 0;
}
}
void build(int index, int l, int r) {
tree[index] = {l, r, 0, 0};
if (l == r) {
tree[index].total = w[r];
return;
}
int mid = l + r >> 1;
build(index << 1, l, mid);
build(index << 1 | 1, mid + 1, r);
tree[index].total = tree[index << 1].total + tree[index << 1 | 1].total;
}
// 其余代码省略...
维护序列问题
通过维护序列的模运算特性，可以实现复杂的数据结构操作。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 100010;
int n, p, m;
int w[N];
struct Node {
int l, r;
LL total;
LL add, mul;
} tree[N * 4];
void apply(Node &node, LL add, LL mul) {
node.total = (node.total * mul + add * (node.r - node.l + 1)) % p;
node.mul = node.mul * mul % p;
node.add = (node.add * mul + add) % p;
}
void pushDown(int index) {
Node &node = tree[index];
if (node.add != 0 || node.mul != 1) {
int left = index << 1;
int right = index << 1 | 1;
apply(tree[left], node.add, node.mul);
apply(tree[right], node.add, node.mul);
node.add = 0;
node.mul = 1;
}
}
void build(int index, int l, int r) {
tree[index] = {l, r, 0, 0, 1};
if (l == r) {
tree[index].total = w[r];
return;
}
int mid = l + r >> 1;
build(index << 1, l, mid);
build(index << 1 | 1, mid + 1, r);
tree[index].total = (tree[index << 1].total + tree[index << 1 | 1].total) % p;
}
// 其余代码省略...
应用场景
在线段树中，这些操作可以高效处理以下场景：
- 区间乘法
- 区间加法
- 区间最大值查询
- 区间求和
- 区间最大公约数查询
- 复杂模运算序列维护
