Advanced Segment Trees
Master persistent segment trees, complex range operations, and advanced segment tree techniques
Overview
Advanced segment tree techniques are core tools for handling complex range problems. This chapter explores persistent segment trees, Li Chao trees, dynamic segment trees, and other advanced techniques for solving complex range queries and updates in world-class competitions.
Core Content
1. Persistent Segment Trees
Persistent segment trees preserve historical versions of data structures, supporting queries on any historical state.
// Persistent segment tree implementation
#include <iostream>
#include <vector>
using namespace std;
struct PersistentSegmentTree {
struct Node {
int left, right, sum;
Node() : left(0), right(0), sum(0) {}
Node(int l, int r, int s) : left(l), right(r), sum(s) {}
};
vector<Node> tree;
vector<int> roots;
int n, nodeCount;
PersistentSegmentTree(vector<int>& arr) {
n = arr.size();
tree.reserve(n * 20); // Reserve enough space
nodeCount = 0;
// Build initial version
roots.push_back(build(arr, 0, n - 1));
}
int build(vector<int>& arr, int l, int r) {
int node = nodeCount++;
tree.push_back(Node());
if (l == r) {
tree[node].sum = arr[l];
} else {
int mid = (l + r) / 2;
tree[node].left = build(arr, l, mid);
tree[node].right = build(arr, mid + 1, r);
tree[node].sum = tree[tree[node].left].sum + tree[tree[node].right].sum;
}
return node;
}
// Create new version (point update)
int update(int prevRoot, int l, int r, int pos, int val) {
int node = nodeCount++;
tree.push_back(Node());
if (l == r) {
tree[node].sum = val;
} else {
int mid = (l + r) / 2;
if (pos <= mid) {
tree[node].left = update(tree[prevRoot].left, l, mid, pos, val);
tree[node].right = tree[prevRoot].right;
} else {
tree[node].left = tree[prevRoot].left;
tree[node].right = update(tree[prevRoot].right, mid + 1, r, pos, val);
}
tree[node].sum = tree[tree[node].left].sum + tree[tree[node].right].sum;
}
return node;
}
// Query historical version
int query(int root, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return tree[root].sum;
int mid = (l + r) / 2;
return query(tree[root].left, l, mid, ql, qr) +
query(tree[root].right, mid + 1, r, ql, qr);
}
// Add new version
void addVersion(int pos, int val) {
int newRoot = update(roots.back(), 0, n - 1, pos, val);
roots.push_back(newRoot);
}
// Query specific version
int queryVersion(int version, int l, int r) {
return query(roots[version], 0, n - 1, l, r);
}
// Get version count
int getVersionCount() {
return roots.size();
}
};
// Persistent array application
class PersistentArray {
private:
PersistentSegmentTree* pst;
public:
PersistentArray(vector<int>& initial) {
pst = new PersistentSegmentTree(initial);
}
void set(int pos, int val) {
pst->addVersion(pos, val);
}
int get(int version, int pos) {
return pst->queryVersion(version, pos, pos);
}
int rangeSum(int version, int l, int r) {
return pst->queryVersion(version, l, r);
}
int getCurrentVersion() {
return pst->getVersionCount() - 1;
}
};
int main() {
vector<int> arr = {1, 2, 3, 4, 5};
PersistentArray pa(arr);
cout << "Initial version range sum[1,3]: "
<< pa.rangeSum(0, 1, 3) << endl;
// Modify position 2 to 10
pa.set(2, 10);
cout << "Version 0 position 2 value: " << pa.get(0, 2) << endl;
cout << "Version 1 position 2 value: " << pa.get(1, 2) << endl;
cout << "Version 1 range sum[1,3]: "
<< pa.rangeSum(1, 1, 3) << endl;
return 0;
}2. Li Chao Segment Tree
Li Chao segment tree specializes in line query problems, supporting dynamic line addition and extremum queries.
// Li Chao segment tree implementation
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
struct Line {
long long k, b; // y = kx + b
int id;
Line() : k(0), b(LLONG_MIN), id(-1) {}
Line(long long _k, long long _b, int _id) : k(_k), b(_b), id(_id) {}
long long eval(long long x) {
return k * x + b;
}
};
class LiChaoTree {
private:
vector<Line> tree;
int n;
// Check if line1 is better than line2 at x
bool better(Line& l1, Line& l2, long long x) {
return l1.eval(x) > l2.eval(x);
}
void update(int node, int l, int r, Line& newLine) {
if (l == r) {
if (better(newLine, tree[node], l)) {
tree[node] = newLine;
}
return;
}
int mid = (l + r) / 2;
bool betterLeft = better(newLine, tree[node], l);
bool betterMid = better(newLine, tree[node], mid);
if (betterMid) {
swap(tree[node], newLine);
}
if (betterLeft != betterMid) {
update(2 * node, l, mid, newLine);
} else {
update(2 * node + 1, mid + 1, r, newLine);
}
}
Line query(int node, int l, int r, long long x) {
if (l == r) {
return tree[node];
}
int mid = (l + r) / 2;
Line result = tree[node];
if (x <= mid) {
Line candidate = query(2 * node, l, mid, x);
if (better(candidate, result, x)) {
result = candidate;
}
} else {
Line candidate = query(2 * node + 1, mid + 1, r, x);
if (better(candidate, result, x)) {
result = candidate;
}
}
return result;
}
public:
LiChaoTree(int size) {
n = 1;
while (n < size) n *= 2;
tree.resize(4 * n);
}
// Add line
void addLine(long long k, long long b, int id) {
Line newLine(k, b, id);
update(1, 0, n - 1, newLine);
}
// Query maximum value at x
pair<long long, int> queryMax(long long x) {
Line result = query(1, 0, n - 1, x);
return {result.eval(x), result.id};
}
};
// Convex hull optimization DP application
class ConvexHullOptimization {
private:
LiChaoTree* lct;
public:
ConvexHullOptimization(int maxX) {
lct = new LiChaoTree(maxX + 1);
}
// Add new transition
void addTransition(long long slope, long long intercept, int id) {
lct->addLine(slope, intercept, id);
}
// Query optimal transition
pair<long long, int> queryOptimal(long long x) {
return lct->queryMax(x);
}
};
// Example: Maximum submatrix problem
long long maxSubmatrixDP(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
long long result = LLONG_MIN;
// Enumerate top and bottom boundaries
for (int top = 0; top < n; top++) {
vector<long long> heights(m, 0);
for (int bottom = top; bottom < n; bottom++) {
// Update height array
for (int j = 0; j < m; j++) {
heights[j] += matrix[bottom][j];
}
// Use Li Chao tree for DP optimization
ConvexHullOptimization cho(m);
vector<long long> dp(m);
dp[0] = heights[0];
cho.addTransition(0, heights[0], 0);
result = max(result, dp[0]);
for (int j = 1; j < m; j++) {
auto [maxVal, fromIdx] = cho.queryOptimal(j);
dp[j] = max(heights[j], maxVal + heights[j]);
cho.addTransition(-j, dp[j], j);
result = max(result, dp[j]);
}
}
}
return result;
}
int main() {
// Test Li Chao segment tree
LiChaoTree lct(100);
// Add line y = 2x + 1
lct.addLine(2, 1, 1);
// Add line y = -x + 10
lct.addLine(-1, 10, 2);
// Add line y = x + 3
lct.addLine(1, 3, 3);
for (int x = 0; x <= 10; x++) {
auto [maxVal, lineId] = lct.queryMax(x);
cout << "x=" << x << ": max=" << maxVal << " (line " << lineId << ")" << endl;
}
// Test matrix DP
vector<vector<int>> matrix = {
{1, -2, 3},
{-1, 4, -2},
{2, -1, 1}
};
cout << "Maximum submatrix sum: "
<< maxSubmatrixDP(matrix) << endl;
return 0;
}3. Dynamic Segment Tree
// Dynamic segment tree
#include <iostream>
#include <unordered_map>
using namespace std;
class DynamicSegmentTree {
private:
struct Node {
long long sum;
int left, right;
Node() : sum(0), left(-1), right(-1) {}
};
vector<Node> tree;
int nodeCount;
long long L, R; // Value range
void pushUp(int node) {
tree[node].sum = 0;
if (tree[node].left != -1) {
tree[node].sum += tree[tree[node].left].sum;
}
if (tree[node].right != -1) {
tree[node].sum += tree[tree[node].right].sum;
}
}
int createNode() {
tree.push_back(Node());
return nodeCount++;
}
void update(int& node, long long l, long long r, long long pos, long long val) {
if (node == -1) {
node = createNode();
}
if (l == r) {
tree[node].sum += val;
return;
}
long long mid = l + (r - l) / 2;
if (pos <= mid) {
update(tree[node].left, l, mid, pos, val);
} else {
update(tree[node].right, mid + 1, r, pos, val);
}
pushUp(node);
}
long long query(int node, long long l, long long r, long long ql, long long qr) {
if (node == -1 || ql > r || qr < l) {
return 0;
}
if (ql <= l && r <= qr) {
return tree[node].sum;
}
long long mid = l + (r - l) / 2;
return query(tree[node].left, l, mid, ql, qr) +
query(tree[node].right, mid + 1, r, ql, qr);
}
public:
DynamicSegmentTree(long long minVal, long long maxVal) {
L = minVal;
R = maxVal;
nodeCount = 0;
tree.reserve(1000000); // Reserve space
}
int root = -1;
void update(long long pos, long long val) {
update(root, L, R, pos, val);
}
long long query(long long l, long long r) {
return query(root, L, R, l, r);
}
// Query k-th smallest
long long kthSmallest(int k) {
return kthSmallest(root, L, R, k);
}
private:
long long kthSmallest(int node, long long l, long long r, int k) {
if (node == -1 || k <= 0) return -1;
if (l == r) {
return l;
}
long long mid = l + (r - l) / 2;
long long leftSum = (tree[node].left == -1) ? 0 : tree[tree[node].left].sum;
if (k <= leftSum) {
return kthSmallest(tree[node].left, l, mid, k);
} else {
return kthSmallest(tree[node].right, mid + 1, r, k - leftSum);
}
}
};
// Weight segment tree application
class WeightSegmentTree {
private:
DynamicSegmentTree* dst;
public:
WeightSegmentTree(long long minVal, long long maxVal) {
dst = new DynamicSegmentTree(minVal, maxVal);
}
// Insert number
void insert(long long val) {
dst->update(val, 1);
}
// Delete number
void remove(long long val) {
dst->update(val, -1);
}
// Count numbers <= val
long long countLE(long long val) {
return dst->query(LLONG_MIN, val);
}
// Find k-th smallest number
long long kthSmallest(int k) {
return dst->kthSmallest(k);
}
// Count numbers in range
long long countRange(long long l, long long r) {
return dst->query(l, r);
}
};
// Range k-th smallest problem
class RangeKthSmallest {
private:
vector<DynamicSegmentTree*> trees;
vector<long long> arr;
int n;
public:
RangeKthSmallest(vector<long long>& data) {
arr = data;
n = arr.size();
trees.resize(n + 1);
// Initialize prefix weight segment trees
for (int i = 0; i <= n; i++) {
trees[i] = new DynamicSegmentTree(LLONG_MIN, LLONG_MAX);
}
// Build prefix sums
for (int i = 0; i < n; i++) {
trees[i + 1] = new DynamicSegmentTree(LLONG_MIN, LLONG_MAX);
// Copy previous version and add new element
for (int j = 0; j <= i; j++) {
trees[i + 1]->update(arr[j], 1);
}
}
}
// Query k-th smallest in range [l,r]
long long queryKth(int l, int r, int k) {
// Use difference of two prefix trees
// Simplified implementation, actually needs persistent weight segment tree
vector<long long> values;
for (int i = l; i <= r; i++) {
values.push_back(arr[i]);
}
sort(values.begin(), values.end());
return values[k - 1];
}
};
int main() {
// Test dynamic segment tree
DynamicSegmentTree dst(-1000000, 1000000);
dst.update(5, 3);
dst.update(10, 2);
dst.update(15, 1);
cout << "Sum of range [5,15]: " << dst.query(5, 15) << endl;
cout << "2nd smallest number: " << dst.kthSmallest(2) << endl;
// Test weight segment tree
WeightSegmentTree wst(-100, 100);
wst.insert(5);
wst.insert(3);
wst.insert(8);
wst.insert(1);
wst.insert(7);
cout << "Count of numbers <= 6: " << wst.countLE(6) << endl;
cout << "3rd smallest number: " << wst.kthSmallest(3) << endl;
return 0;
}Problem-Solving Tips
πΎ Space Optimization
Pay attention to space usage in persistent structures, avoid unnecessary node creation in dynamic trees, estimate space requirements reasonably.
β‘ Performance Considerations
Li Chao trees are suitable for line queries, weight segment trees handle k-th smallest problems, choose appropriate advanced segment trees based on problem characteristics.
π§ Implementation Tricks
Pay attention to boundary handling and special cases, design node structures reasonably, use object pools to optimize memory allocation.
π― Application Scenarios
Persistent structures handle historical queries, Li Chao trees optimize DP transitions, dynamic trees handle large sparse data ranges.