线段树高级应用与实现技巧
概述
本文深入探讨线段树的高级应用与实现技巧，涵盖动态开点、离散化、可持久化、区间染色、扫描线及前缀最大值维护等内容，适合具备基础数据结构知识的读者阅读。
动态开点线段树
动态开点技术解决了传统线段树空间需求过大的问题。核心思想是在需要时才创建节点，从而节省空间。
struct DynamicSegmentTree {
struct Node {
int left, right, val, tag;
};
Node tree[4 * N];
int cnt;
void pushdown(int p, int l, int r) {
if (tree[p].tag != 0) {
int mid = (l + r) / 2;
tree[2p].val += (mid - l + 1) * tree[p].tag;
tree[2p].tag += tree[p].tag;
tree[2p + 1].val += (r - mid) * tree[p].tag;
tree[2p + 1].tag += tree[p].tag;
tree[p].tag = 0;
}
}
void update(int l, int r, int pos, int &p, int d) {
if (!p) {
p = ++cnt;
tree[p].val = 0;
tree[p].tag = 0;
}
if (l == r) {
tree[p].val += d;
return;
}
pushdown(p, l, r);
int mid = (l + r) / 2;
if (pos <= mid) update(l, mid, pos, tree[p].left, d);
else update(mid + 1, r, pos, tree[p].right, d);
tree[p].val = tree[tree[p].left].val + tree[tree[p].right].val;
}
};
离散化处理
离散化技术用于处理数据范围过大问题，通过压缩坐标减少空间需求。
void discretize() {
sort(all(candidates));
int size = unique(candidates.begin(), candidates.end()) - candidates.begin();
for (int &x : values) {
x = lower_bound(candidates.begin(), candidates.end(), x) - candidates.begin();
}
}
可持久化线段树
可持久化技术允许记录线段树的历史版本，适用于需要多次版本回溯的场景。
struct PersistentSegmentTree {
struct Node {
int left, right, val, tag;
Node *leftChild, *rightChild;
};
vector nodes;
Node* pushdown(Node* p, int l, int r) {
if (!p) return nullptr;
if (p->tag != 0) {
int mid = (l + r) / 2;
Node* left = new Node();
left->val = p->val * (mid - l + 1);
left->tag = p->tag;
Node* right = new Node();
right->val = p->val * (r - mid);
right->tag = p->tag;
p->leftChild = left;
p->rightChild = right;
p->tag = 0;
}
return p;
}
Node* update(Node* p, int l, int r, int pos, int d) {
if (!p) {
p = new Node();
p->val = 0;
p->tag = 0;
p->leftChild = nullptr;
p->rightChild = nullptr;
}
if (l == r) {
p->val += d;
return p;
}
p = pushdown(p, l, r);
int mid = (l + r) / 2;
if (pos <= mid) p->leftChild = update(p->leftChild, l, mid, pos, d);
else p->rightChild = update(p->rightChild, mid + 1, r, pos, d);
p->val = (p->leftChild ? p->leftChild->val : 0) + (p->rightChild ? p->rightChild->val : 0);
return p;
}
};
区间染色与查询
区间染色问题需要维护区间颜色状态，支持区间查询。
struct ColorSegmentTree {
struct Node {
int left, right, color, val;
};
Node tree[4 * N];
void pushdown(int p, int l, int r) {
if (tree[p].color != -1) {
int mid = (l + r) / 2;
tree[2p].color = tree[p].color;
tree[2p].val = (mid - l + 1) * tree[p].color;
tree[2p + 1].color = tree[p].color;
tree[2p + 1].val = (r - mid) * tree[p].color;
tree[p].color = -1;
}
}
void update(int l, int r, int pos, int d, int p) {
if (l == r) {
tree[p].color = d;
tree[p].val = d;
return;
}
pushdown(p, l, r);
int mid = (l + r) / 2;
if (pos <= mid) update(l, mid, pos, d, 2p);
else update(mid + 1, r, pos, d, 2p + 1);
tree[p].val = tree[2p].val + tree[2p + 1].val;
}
};
扫描线与矩形面积并
扫描线技术用于处理动态几何问题，通过离散化和线段树维护扫描过程中的状态。
#include <vector>
#include <algorithm>
struct Line {
int x1, x2, y;
bool isUpper;
Line(int x1, int x2, int y, bool isUpper) : x1(x1), x2(x2), y(y), isUpper(isUpper) {}
};
void scanLine() {
vector<Line> lines;
// 添加所有边
sort(lines.begin(), lines.end(), [](const Line& a, const Line& b) { return a.y < b.y; });
vector<int> coords;
for (const auto& line : lines) {
coords.push_back(line.x1);
coords.push_back(line.x2);
}
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());
// 初始化线段树
// 扫描处理
}
维护前缀最大值
线段树可以维护区间前缀最大值，支持区间查询和单点修改。
struct MaxSegmentTree {
struct Node {
int left, right, maxVal;
};
Node tree[4 * N];
void build(int l, int r, int p) {
if (l == r) {
tree[p].maxVal = a[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, 2p);
build(mid + 1, r, 2p + 1);
tree[p].maxVal = max(tree[2p].maxVal, tree[2p + 1].maxVal);
}
void query(int l, int r, int p, int &ans) {
if (l > r) return;
if (l == r) {
ans = max(ans, tree[p].maxVal);
return;
}
int mid = (l + r) / 2;
query(l, mid, 2p, ans);
query(mid + 1, r, 2p + 1, ans);
}
};
