Li Chao Segment Tree

Problem: Maintain a collection S of linear functions with the following operations:

• Insert a linear function f(x) = kx + b over a range [l, r]
• Query maxf∈S f(x) for a given x

The naive approach decomposes a linear function's range into O(log n) segment tree nodes and stores all functions at each node. However, this can lead to excessive memory usage and degraded performance when many functions accumulate at the same node.

The optimized approach maintains at most one function per node. When a new function conflicts with the existing one at a node, we compare them to determine their dominance intervals. Only one function can dominate the current interval, so the losing function is pushed down to its dominance region. Since this recursive descent occurs only on one side, each resolution costs O(log n).

Each insertion requires decomposing the range into O(log n) intervals, yielding O(log² n) per insertion. Query operations remain O(log n). This results in O(m log² n) total complexity for m operations.

Notably, certain DP optimizations with slope transformation are equivalent to inserting linear functions and querying single points. Since these are global operations without range decomposition, complexity drops to O(n log n), outperforming CDQ divide and conquer and balanced tree approaches.

Example Implementation

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 1e5 + 10;
const long double EPS = 1e-9;

struct Line {
    long double slope, intercept;
    void build(int x1, int x2, int y1, int y2) {
        if (x1 == x2) {
            slope = 0;
            intercept = max(y1, y2);
        } else {
            slope = 1.0L * (y2 - y1) / (x2 - x1);
            intercept = y1 - 1.0L * x1 * slope;
        }
    }
    double evaluate(int x) const {
        return slope * x + intercept;
    }
};

Line lines[MAXN];

int compare(double a, double b) {
    if (b - a > EPS) return 0;
    if (a - b > EPS) return 1;
    return 2;
}

int getMaxId(int id1, int id2, int x) {
    int result = compare(lines[id1].evaluate(x), lines[id2].evaluate(x));
    if (result == 2) return min(id1, id2);
    return result ? id1 : id2;
}

struct SegmentTree {
    int tag[MAXN << 2];
    #define LEFT(idx) (idx << 1)
    #define RIGHT(idx) (idx << 1 | 1)
    #define MID(l, r) ((l + r) >> 1)
    
    void update(int node, int l, int r, int lineId) {
        if (!tag[node]) {
            tag[node] = lineId;
            return;
        }
        int mid = MID(l, r);
        if (getMaxId(lineId, tag[node], mid) == lineId)
            swap(lineId, tag[node]);
        if (l == r) return;
        if (getMaxId(lineId, tag[node], l) == lineId)
            update(LEFT(node), l, mid, lineId);
        if (getMaxId(lineId, tag[node], r) == lineId)
            update(RIGHT(node), mid + 1, r, lineId);
    }
    
    void insertRange(int node, int l, int r, int ql, int qr, int lineId) {
        if (ql <= l && r <= qr) {
            update(node, l, r, lineId);
            return;
        }
        int mid = MID(l, r);
        if (ql <= mid) insertRange(LEFT(node), l, mid, ql, qr, lineId);
        if (mid < qr) insertRange(RIGHT(node), mid + 1, r, ql, qr, lineId);
    }
    
    int query(int node, int l, int r, int x) {
        if (l == r) return tag[node];
        int mid = MID(l, r);
        if (x <= mid) return getMaxId(tag[node], query(LEFT(node), l, mid, x), x);
        return getMaxId(tag[node], query(RIGHT(node), mid + 1, r, x), x);
    }
} seg;

int n, lineCount, bound = 39990;

void addMod(int& x, int y, int mod) {
    x = (x + y - 1) % mod + 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int lastAns = 0;
    while (n--) {
        int opt; cin >> opt;
        if (opt == 0) {
            int pos; cin >> pos;
            addMod(pos, lastAns, 39989);
            cout << (lastAns = seg.query(1, 1, bound, pos)) << "\n";
        } else {
            int x0, y0, x1, y1;
            cin >> x0 >> y0 >> x1 >> y1;
            addMod(x0, lastAns, 39989);
            addMod(x1, lastAns, 39989);
            addMod(y0, lastAns, 1000000000);
            addMod(y1, lastAns, 1000000000);
            lines[++lineCount].build(x0, x1, y0, y1);
            seg.insertRange(1, 1, bound, min(x0, x1), max(x0, x1), lineCount);
        }
    }
    return 0;
}

Li Chao trees support efficient merging by merging tags and propagating down, and undo operations work naturally since they don't require amortization.

Segment Tree Merge

Problem: Maintain n elements where initially each belongs to its own set. Operations include merging two sets and querying specific sets.

Dynamic segment trees efficiently maintain sets. When merging two dynamic segment trees, only overlapping nodes require processing, costing "overlap count" operations. Each merge reduces total node count by the overlap amount. Since total nodes are O(n log n), amortized complexity becomes O(n log n).

Consider problem P3224: islands and rankings. Connecting two islands merges their connected components, maintained with union-find. Each component stores a value segment tree. Merging components only processes overlapping nodes, achieving both O(n log n) time and space complexity.

Implementation Example

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

int n, m, parent[MAXN], rankArr[MAXN];
int findRoot(int x) {
    return parent[x] = (parent[x] == x) ? x : findRoot(parent[x]);
}

struct Node {
    int left, right, cnt;
} segNode[MAXN << 5];
int nodePtr, garbage[MAXN << 5], garbageTop;

int allocateNode() {
    return garbageTop ? garbage[garbageTop--] : ++nodePtr;
}

struct SegTree {
    int root;
    #define MID(l, r) ((l + r) >> 1)
    
    void pull(int idx) {
        segNode[idx].cnt = segNode[segNode[idx].left].cnt + segNode[segNode[idx].right].cnt;
    }
    
    void initNode(int val, int l, int r, int target) {
        root = build(l, r, target);
    }
    
    int build(int l, int r, int target) {
        int idx = allocateNode();
        segNode[idx].cnt = 1;
        if (l == r) return idx;
        int mid = MID(l, r);
        if (target <= mid) segNode[idx].left = build(l, mid, target);
        else segNode[idx].right = build(mid + 1, r, target);
        pull(idx);
        return idx;
    }
    
    int kth(int idx, int l, int r, int k) {
        if (segNode[idx].cnt < k) return -1;
        if (l == r) return rankArr[l];
        int mid = MID(l, r);
        int leftCnt = segNode[segNode[idx].left].cnt;
        if (leftCnt >= k) return kth(segNode[idx].left, l, mid, k);
        return kth(segNode[idx].right, mid + 1, r, k - leftCnt);
    }
    
    int merge(int idx1, int idx2, int l, int r) {
        if (!idx1 || !idx2) return idx1 + idx2;
        if (l == r) {
            segNode[idx1].cnt += segNode[idx2].cnt;
            garbage[++garbageTop] = idx2;
            return idx1;
        }
        int mid = MID(l, r);
        segNode[idx1].left = merge(segNode[idx1].left, segNode[idx2].left, l, mid);
        segNode[idx1].right = merge(segNode[idx1].right, segNode[idx2].right, mid + 1, r);
        pull(idx1);
        garbage[++garbageTop] = idx2;
        return idx1;
    }
} forest[MAXN];

void unite(int x, int y) {
    int fx = findRoot(x), fy = findRoot(y);
    if (fx == fy) return;
    parent[fy] = fx;
    forest[fx].root = forest[fx].merge(forest[fx].root, forest[fy].root, 1, n);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        rankArr[x] = i;
        forest[i].initNode(x, 1, n, x);
        parent[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        unite(u, v);
    }
    int T; cin >> T;
    while (T--) {
        char cmd; int x, y;
        cin >> cmd >> x >> y;
        if (cmd == 'Q')
            cout << forest[findRoot(x)].kth(forest[findRoot(x)].root, 1, n, y) << "\n";
        else
            unite(x, y);
    }
    return 0;
}

Segment tree merge also optimizes tree DP. Consider problem P6847 with O(nk) brute force DP. Let f(u,i) represent maximum juice considering subtree of u within time ≤ i. Two transitions exist:

• Don't cut edge to parent: f(u,i) = Σ f(v,i) for v in subtree(u)
• Cut edge: ∀ i ∈ [d_u, k], f(u,i) = max(f(u,i), Σ f(v, d_u) + w_u)

Use time-indexed segment trees for f(u). After merging child segment trees, the second transition becomes range max operations. Since f(u,i) is non-decreasing, each operation finds the largest c where i ∈ [d_u, c] and f(u,i) ≤ val, setting [d_u, c] to val. Segment tree merge requires lazy propagation without node creation overhead, so use "tag persistence" with additive tags only—range assignment transforms to range flattening plus range addition.

DP Optimization Code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 1e5 + 10;

struct Edge {
    int to, next;
} edges[MAXN << 1];
int head[MAXN], edgeCnt;

void addEdge(int u, int v) {
    edges[++edgeCnt] = {v, head[u]};
    head[u] = edgeCnt;
}

int n, m, k, deadline[MAXN], profit[MAXN];

struct Node {
    int left, right, maxVal, minVal, lazy;
} segNode[MAXN << 5];
int poolTop, recycled[MAXN << 5];
int newNode() {
    return poolTop ? recycled[poolTop--] : ++poolTop;
}
void reclaim(int& idx) {
    if (!idx) return;
    segNode[idx] = {0, 0, 0, 0, 0};
    recycled[++poolTop] = idx;
    idx = 0;
}

struct SegTree {
    int root;
    #define MID(l, r) ((l + r) >> 1)
    
    void push(int idx) {
        segNode[idx].maxVal = max(segNode[segNode[idx].left].maxVal, 
                                  segNode[segNode[idx].right].maxVal) + segNode[idx].lazy;
        segNode[idx].minVal = min(segNode[segNode[idx].left].minVal,
                                  segNode[segNode[idx].right].minVal) + segNode[idx].lazy;
    }
    
    void merge(int& idx1, int& idx2, int l, int r) {
        if (!idx1 || !idx2) {
            idx1 = idx1 + idx2;
            return;
        }
        if (l == r) {
            segNode[idx1].lazy += segNode[idx2].lazy;
            reclaim(idx2);
            segNode[idx1].maxVal = segNode[idx1].minVal = segNode[idx1].lazy;
            return;
        }
        segNode[idx1].lazy += segNode[idx2].lazy;
        merge(segNode[idx1].left, segNode[idx2].left, l, MID(l, r));
        merge(segNode[idx1].right, segNode[idx2].right, MID(l, r) + 1, r);
        push(idx1);
        reclaim(idx2);
    }
    
    void assign(int& idx, int l, int r, int from, int val) {
        if (!idx) idx = newNode();
        if (from <= l) {
            if (segNode[idx].maxVal <= val) {
                reclaim(segNode[idx].left);
                reclaim(segNode[idx].right);
                segNode[idx].lazy = segNode[idx].maxVal = segNode[idx].minVal = val;
                return;
            } else {
                val -= segNode[idx].lazy;
                if (segNode[segNode[idx].left].minVal < val)
                    assign(segNode[idx].left, l, MID(l, r), from, val);
                if (segNode[segNode[idx].right].minVal < val)
                    assign(segNode[idx].right, MID(l, r) + 1, r, from, val);
                push(idx);
                return;
            }
        }
        val -= segNode[idx].lazy;
        if (from <= MID(l, r)) assign(segNode[idx].left, l, MID(l, r), from, val);
        assign(segNode[idx].right, MID(l, r) + 1, r, from, val);
        push(idx);
    }
    
    int queryPoint(int idx, int l, int r, int x) {
        if (!idx) return 0;
        if (l == r) return segNode[idx].lazy;
        int mid = MID(l, r);
        if (x <= mid) return segNode[idx].lazy + queryPoint(segNode[idx].left, l, mid, x);
        return segNode[idx].lazy + queryPoint(segNode[idx].right, mid + 1, r, x);
    }
    
    int queryAll() { return segNode[root].maxVal; }
} trees[MAXN];

void dfs(int u, int parent) {
    for (int i = head[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (v == parent) continue;
        dfs(v, u);
        trees[u].merge(trees[u].root, trees[v].root, 1, k);
    }
    if (deadline[u]) {
        int base = profit[u] + trees[u].queryPoint(trees[u].root, 1, k, deadline[u]);
        trees[u].assign(trees[u].root, 1, k, deadline[u], base);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        addEdge(p, i);
        addEdge(i, p);
    }
    for (int i = 1; i <= m; i++) {
        int v; cin >> v;
        cin >> deadline[v] >> profit[v];
    }
    dfs(1, 0);
    cout << trees[1].queryAll() << "\n";
    return 0;
}

Segment Tree Divide and Conquer

This technique trades an extra O(log n) factor to transform offline insert-query-delete problems into insert-query-revert problems. When a problem allows efficient modification and querying via data structure S but S only supports reversion (not deletion), segment tree divide and conquer provides a solution.

For each time interval [l_i, r_i] where element i exists, insert i into all segment tree nodes covering [l_i, r_i]. Then traverse the segment tree:

1. Insert all elements attached to the current node into global structure S
2. If at a leaf node corresponding to a query time, answer that query
3. Recursively process left and right children
4. Revert all changes made in step 1

DataStruct S {
    void add(Element e);
    void query(Info& ans);
    int snapshot();
    void restore(int state);
};

void solve(node, l, r) {
    int savedState = S.snapshot();
    for (Element e : node.elements) S.add(e);
    if (l == r) {
        answer[l] = S.query(query[l]);
        return;
    }
    solve(leftChild, l, mid);
    solve(rightChild, mid + 1, r);
    S.restore(savedState);
}

Cat Tree Divide and Conquer

For mergeable information U where combining U₁ and U₂ is expensive but adding a new element to U is cheap, cat tree divide and conquer reduces merge overhead.

For range [l, r], process queries fully contained within it. First solve left and right subranges. Then handle queries crossing the midpoint. Each such query decomposes into a suffix ending at mid-1 and a prefix starting at mid. Precomputing all suffix and prefix information allows O(1) combination.

Example: Given sequence a and modulo m, count subsequences with sum divisible by m in q queries. Direct segment tree with knapsack gives O(nm² log n). Cat tree divide and conquer achieves O(nm log n) since adding one element to a knapsack costs O(m) and combining results also costs O(m).

Implementation

#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;

int n, mod, Q, arr[MAXN], result[MAXN];

struct Knapsack {
    int dp[20];
    Knapsack() { dp[0] = 1; fill(dp + 1, dp + 20, 0); }
} prefixState[MAXN];

void addMod(int& x, int y) { x = (x + y) % MOD; }

void addToKnapsack(Knapsack& state, int val) {
    Knapsack next;
    for (int i = 0; i < 20; i++) next.dp[i] = state.dp[i];
    for (int i = 0; i < 20; i++) 
        addMod(next.dp[(i + val) % mod], state.dp[i]);
    state = next;
}

struct Query {
    int l, r, idx;
};

namespace CatTree {
    #define LEFT(idx) (idx << 1)
    #define RIGHT(idx) (idx << 1 | 1)
    #define MID(l, r) ((l + r) >> 1)
    
    vector<Query> queries[MAXN << 2];
    vector<Query> leftQueries[MAXN], rightQueries[MAXN];
    
    void clearVec(vector<Query>& v) { vector<Query>().swap(v); }
    
    void addQuery(int node, int l, int r, int ql, int qr, int qid) {
        if ((ql <= MID(l, r) && MID(l, r) < qr) || l == r) {
            queries[node].push_back({ql, qr, qid});
            return;
        }
        if (ql <= MID(l, r)) addQuery(LEFT(node), l, MID(l, r), ql, qr, qid);
        else addQuery(RIGHT(node), MID(l, r) + 1, r, ql, qr, qid);
    }
    
    void solve(int node, int l, int r) {
        if (l == r) {
            for (auto& q : queries[node]) 
                result[q.idx] = 1 + (arr[l] == 0);
            return;
        }
        solve(LEFT(node), l, MID(l, r));
        solve(RIGHT(node), MID(l, r) + 1, r);
        
        for (auto& q : queries[node]) {
            leftQueries[q.l].push_back(q);
            rightQueries[q.r].push_back(q);
        }
        
        Knapsack leftState, rightState;
        for (int i = MID(l, r); i >= l; i--) {
            addToKnapsack(leftState, arr[i]);
            for (auto& q : leftQueries[i])
                prefixState[q.idx] = leftState;
        }
        
        for (int i = MID(l, r) + 1; i <= r; i++) {
            addToKnapsack(rightState, arr[i]);
            for (auto& q : rightQueries[i]) {
                int id = q.idx;
                for (int j = 0; j < mod; j++)
                    addMod(result[id], prefixState[id].dp[j] * rightState.dp[(mod - j) % mod] % MOD);
            }
        }
        
        for (auto& q : queries[node]) {
            clearVec(leftQueries[q.l]);
            clearVec(rightQueries[q.r]);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> mod;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        arr[i] %= mod;
    }
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        int l, r; cin >> l >> r;
        CatTree::addQuery(1, 1, n, l, r, i);
    }
    CatTree::solve(1, 1, n);
    for (int i = 1; i <= Q; i++) cout << result[i] << "\n";
    return 0;
}

Segbeats

Segbeats solves range min/max assignment operations: for range [l, r] and value v, set aᵢ ← min(aᵢ, v). Each operation maintains range sums and other aggregates.

Standard segment trees cannot efficiently handle this. The elegant pruning by Ji Ruyi handles this: for node o representing [lₒ, rₒ], maintain minimum mnₒ and strict second minimum seₒ. For operation with value v:

• If mnₒ ≥ v: no change needed
• If mnₒ ≤ v < seₒ: set mnₒ ← v
• If seₒ ≤ v: recursively update children

Complexity analysis shows O(n log n) total for n operations. The key insight is that only case 3 triggers expensive operations, and each trigger reduces distinct values in the node's range. Since sum of value counts across all nodes is O(n log n), case 3 triggers O(n log n) times maximum.

Segbeats with range addition achieves O(n log² n) complexity.

Matrix Semigroup Approach

When segment trees accumulate diverse tags and maintenance information, human analysis becomes intractable. Matrix-based semigroups offer a systematic solution: design a matrix representation capturing all necessary information as a semigroup, allowing automatic composition of operations.

Since matrices form a semigroup under multiplication, complex segment tree operations reduce to matrix multiplication and application.

Leftist Heap

Leftist heaps are mergeable priority queues with O(log n) merge without heuristic balancing.

Merge process:

• When roots conflict, select the better root as parent
• Recursively merge the selected parent's child subtree with the other tree
• Return the other tree when one is empty

Define a node's "height" as distance to nearest leaf. A leftist heap satisfies d(right subtree) ≤ d(left subtree), guaranteeing d(u) = d(right) + 1.

For n-node leftist heap with distance T(n), the smaller subtree has size ≤ n/2, yielding T(n) = T(⌊n/2⌋) + 1, so T(n) = O(log n).

Template Implementation

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN = 1e5 + 10;

struct HeapNode {
    int left, right, val, id, dist, parent;
} h[MAXN];

bool operator<(const HeapNode& a, const HeapNode& b) {
    if (a.val != b.val) return a.val < b.val;
    return a.id < b.id;
}

int n, m, deleted[MAXN];

int findRoot(int x) {
    return h[x].parent = (h[x].parent == x) ? x : findRoot(h[x].parent);
}

void update(int idx) {
    if (h[h[idx].right].dist > h[h[idx].left].dist)
        swap(h[idx].left, h[idx].right);
    h[idx].dist = h[h[idx].right].dist + 1;
}

int merge(int a, int b) {
    if (!a || !b) {
        h[a + b].dist = 0;
        return a + b;
    }
    if (h[b] < h[a]) swap(a, b);
    h[a].right = merge(h[a].right, b);
    update(a);
    return a;
}

void unionSets(int x, int y) {
    if (deleted[x] || deleted[y]) return;
    x = findRoot(x);
    y = findRoot(y);
    if (x == y) return;
    h[x].parent = h[y].parent = merge(x, y);
}

void pop(int x) {
    if (deleted[x]) {
        cout << -1 << "\n";
        return;
    }
    x = findRoot(x);
    cout << h[x].val << "\n";
    deleted[x] = 1;
    h[h[x].left].parent = h[h[x].right].parent = 
        h[x].parent = merge(h[x].left, h[x].right);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    h[0].dist = -1;
    for (int i = 1; i <= n; i++) {
        cin >> h[i].val;
        h[i].id = i;
        h[i].parent = i;
    }
    while (m--) {
        int op; cin >> op;
        if (op == 1) {
            int u, v; cin >> u >> v;
            unionSets(u, v);
        } else {
            int u; cin >> u;
            pop(u);
        }
    }
    return 0;
}