Dynamic node creation is used when the value range is large (e.g., 1e9) to conserve memory and avoid waste. Nodes are allocated only when needed, and queries return immediately upon reaching a null node.

void update(int& node, int left, int right, int pos, int delta) {
    if (!node) node = ++node_cnt;
    if (left == right) {
        sum[node] += delta;
        return;
    }
    int mid = left + ((right - left) >> 1);
    if (pos <= mid)
        update(lc[node], left, mid, pos, delta);
    else
        update(rc[node], mid + 1, right, pos, delta);
    sum[node] = sum[lc[node]] + sum[rc[node]];
}
int query(int node, int left, int right, int ql, int qr) {
    if (!node) return 0;
    if (ql <= left && right <= qr) return sum[node];
    int mid = left + ((right - left) >> 1), res = 0;
    if (ql <= mid) res += query(lc[node], left, mid, ql, qr);
    if (qr > mid) res += query(rc[node], mid + 1, right, ql, qr);
    return res;
}

Lazy tags are not propagated but remain permanently on nodes. There is no need for pushdown or pushup operations.

Conditions for use:

• Modifications must allow quick updates (e.g., min/max, sum).
• Modifications must be order-independent.

Primary application: Persistent segment trees where different versions share nodes. Propagating tags would mix versions, so permanent tags are necessary for range modifications.

Reference template for range addition:

1. Modification

void modify(int node, int l, int r, int ql, int qr, int val) {
    tree[node].sum += (min(r, qr) - max(l, ql) + 1) * val;
    if (ql <= l && r <= qr) {
        tree[node].tag += val;
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid)
        modify(tree[node].left, l, mid, ql, qr, val);
    if (qr > mid)
        modify(tree[node].right, mid + 1, r, ql, qr, val);
}

2. Range sum query

int query(int node, int l, int r, int ql, int qr, int carry) {
    if (ql <= l && r <= qr)
        return tree[node].sum + (min(r, qr) - max(l, ql) + 1) * carry;
    int mid = (l + r) >> 1, res = 0;
    carry += tree[node].tag;
    if (ql <= mid)
        res += query(tree[node].left, l, mid, ql, qr, carry);
    if (qr > mid)
        res += query(tree[node].right, mid + 1, r, ql, qr, carry);
    return res;
}

Segment Tree Merging

Merge two segment trees Tx and Ty into Tz. To maintain efficiency, if either node is null, return the non-null one. Otherwise, create a new node z as the merged result and recursively merge children.

int merge(int l, int r, int x, int y) {
    if (!x || !y) return x | y;
    int mid = (l + r) >> 1, z = ++total_nodes;
    if (l == r) {
        sum[z] = sum[x] + sum[y];
        return z;
    }
    tree[z].left = merge(l, mid, tree[x].left, tree[y].left);
    tree[z].right = merge(mid + 1, r, tree[x].right, tree[y].right);
    pushup(z);
    return z;
}

Time complexity: O(n log n) for merging two full trees. Since nodes are not repeatedly merged, total complexity is approximately O(n log n).

Applicability: Check if leaf nodes can be merged quickly and pushup is efficient. Most segment tree problems satisfy these conditions.

Note:

1. Merging is permanent.
2. Complexity is amortized; not suitable for DAGs.

Segment Tree Splitting

Split by value or size. Let k be the split value/size, x the original tree, and y the new tree. Let v be the value/size of the left subtree.

• If k < v: Right subtree of x is entirely greater than k, assign x's right subtree too y, recurse left.
• If k = v: Left subtree satisfies condition, assign x's right subtree to y.
• If k > v: Left part of x remains unchanged, recurse right.

Example by size:

void split(int x, int &y, int k) {
    if (!x) return;
    y = new_node();
    long long v = tree[tree[x].left].size;
    if (k > v)
        split(tree[x].right, tree[y].right, k - v);
    else
        swap(tree[x].right, tree[y].right);
    if (k < v)
        split(tree[x].left, tree[y].left, k);
    tree[y].size = tree[x].size - k;
    tree[x].size = k;
}

Binary Search on Segment Tree

Utilize the divide-and-conquer structure of segment trees for binary search.

Example: Single-point modification, global query. Given a non-negative sequence of length n, support single-point updates. For Q queries, find the first position where prefix sum exceeds x.

Since prefix sums are monotonic, binary search can be performed directly on the segment tree.

For interval queries [x, y]:

int query(int node, int ql, int qr, int limit, int &accum) {
    if (ql <= L[node] && R[node] <= qr) {
        if (accum + value[node] <= limit) {
            accum += value[node];
            return -1;
        }
        if (L[node] == R[node]) return L[node];
    }
    int mid = (L[node] + R[node]) >> 1;
    if (ql <= mid) {
        int res = query(node << 1, ql, qr, limit, accum);
        if (res != -1) return res;
    }
    if (mid < qr) return query(node << 1 | 1, ql, qr, limit, accum);
    return -1;
}

FHQ Treap

A balanced binary search tree based on split and merge operations.

Node structure:

struct Node {
    int left, right, value, priority, size;
} tree[N];

Create new node:

int create_node(int val) {
    int id = ++node_count;
    tree[id].value = val;
    tree[id].size = 1;
    tree[id].priority = rand();
    return id;
}

Update size:

void pushup(int x) {
    tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
}

Split by value:

void split(int cur, int val, int &x, int &y) {
    if (!cur) {
        x = y = 0;
        return;
    }
    if (tree[cur].value <= val) {
        x = cur;
        split(tree[cur].right, val, tree[cur].right, y);
    } else {
        y = cur;
        split(tree[cur].left, val, x, tree[cur].left);
    }
    pushup(cur);
}

Merge:

int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (tree[x].priority < tree[y].priority) {
        tree[y].left = merge(x, tree[y].left);
        pushup(y);
        return y;
    } else {
        tree[x].right = merge(tree[x].right, y);
        pushup(x);
        return x;
    }
}

Insert value:

void insert(int val) {
    int x = 0, y = 0;
    split(root, val - 1, x, y);
    root = merge(merge(x, create_node(val)), y);
}

Delete value:

void remove(int val) {
    int x = 0, y = 0, z = 0;
    split(root, val, x, z);
    split(x, val - 1, x, y);
    y = merge(tree[y].left, tree[y].right);
    root = merge(merge(x, y), z);
}

Find k-th largest:

int kth(int k) {
    int cur = root;
    while (true) {
        if (k <= tree[tree[cur].left].size)
            cur = tree[cur].left;
        else if (k == tree[tree[cur].left].size + 1)
            return tree[cur].value;
        else {
            k -= tree[tree[cur].left].size + 1;
            cur = tree[cur].right;
        }
    }
}

Get rank of value:

int get_rank(int val) {
    int x = 0, y = 0;
    split(root, val - 1, x, y);
    int res = tree[x].size + 1;
    root = merge(x, y);
    return res;
}

Predecessor:

int predecessor(int val) {
    int cur = root, res = 0;
    while (cur) {
        if (val <= tree[cur].value)
            cur = tree[cur].left;
        else {
            res = tree[cur].value;
            cur = tree[cur].right;
        }
    }
    return res;
}

Successor:

int successor(int val) {
    int cur = root, res = 0;
    while (cur) {
        if (val >= tree[cur].value)
            cur = tree[cur].right;
        else {
            res = tree[cur].value;
            cur = tree[cur].left;
        }
    }
    return res;
}

Example: Interval Reversal with FHQ Treap

Maintain intervals using in-order traversal. Split the target interval by size, apply a reversal tag, then merge.

void pushdown(int x) {
    if (!tree[x].tag) return;
    tree[tree[x].left].tag ^= 1;
    tree[tree[x].right].tag ^= 1;
    swap(tree[x].left, tree[x].right);
    tree[x].tag = 0;
}
void reverse(int l, int r) {
    int x = 0, y = 0, z = 0;
    split(root, r, x, z);
    split(x, l - 1, x, y);
    tree[y].tag ^= 1;
    root = merge(x, merge(y, z));
}