Linear Operation Segment Trees

The most basic form of segment tree handles linear operations that satisfy commutativity and associativity, such as addition. Since operations do not depend on each other, maintaining lazy propagation is straightforward. For single-point modifications, a Fenwick Tree (Binary Indexed Tree) is often a more efficient alternative.

Implementation

#define LEFT(u) (u * 2)
#define RIGHT(u) (u * 2 + 1)

struct TreeNode {
    long long sum;
    long long add_pending;
} tree[4 * MAX];

void construct(int node, int start, int end) {
    if (start == end) {
        tree[node].sum = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    construct(LEFT(node), start, mid);
    construct(RIGHT(node), mid + 1, end);
    tree[node].sum = tree[LEFT(node)].sum + tree[RIGHT(node)].sum;
}

void apply_lazy(int node, int start, int end, long long value) {
    tree[node].sum += value * (end - start + 1);
    tree[node].add_pending += value;
}

void push_down(int node, int start, int end) {
    if (tree[node].add_pending == 0) return;
    
    int mid = (start + end) / 2;
    apply_lazy(LEFT(node), start, mid, tree[node].add_pending);
    apply_lazy(RIGHT(node), mid + 1, end, tree[node].add_pending);
    tree[node].add_pending = 0;
}

void range_update(int node, int start, int end, int l, int r, long long val) {
    if (l > end || r < start) return;
    if (l <= start && end <= r) {
        apply_lazy(node, start, end, val);
        return;
    }
    push_down(node, start, end);
    int mid = (start + end) / 2;
    range_update(LEFT(node), start, mid, l, r, val);
    range_update(RIGHT(node), mid + 1, end, l, r, val);
    tree[node].sum = tree[LEFT(node)].sum + tree[RIGHT(node)].sum;
}

long long range_query(int node, int start, int end, int l, int r) {
    if (l > end || r < start) return 0;
    if (l <= start && end <= r) return tree[node].sum;
    
    push_down(node, start, end);
    int mid = (start + end) / 2;
    return range_query(LEFT(node), start, mid, l, r) + 
           range_query(RIGHT(node), mid + 1, end, l, r);
}

Non-Linear Operations with Dependent Marks

This category handles operations where order matters, such as combining range addition and range multiplciation. You cannot simply swap these operations; for example, (x + a) * b differs from (x * b) + a. The standard approach is to enforce a fixed priority: multiplication over addition. When a multiplication mark is applied, it must also scale the existing addition mark to preserve correctness.

Implementation

struct OpNode {
    long long total;
    long long add_mark;
    long long mul_mark;
} seg[4 * MAX];

void build_tree(int idx, int lo, int hi) {
    seg[idx].add_mark = 0;
    seg[idx].mul_mark = 1;
    if (lo == hi) {
        seg[idx].total = arr[lo] % MOD;
        return;
    }
    int mid = (lo + hi) / 2;
    build_tree(LEFT(idx), lo, mid);
    build_tree(RIGHT(idx), mid + 1, hi);
    seg[idx].total = (seg[LEFT(idx)].total + seg[RIGHT(idx)].total) % MOD;
}

void propagate(int idx, int lo, int hi) {
    int mid = (lo + hi) / 2;
    int left_len = mid - lo + 1;
    int right_len = hi - mid;

    // Apply to left child
    seg[LEFT(idx)].total = (seg[LEFT(idx)].total * seg[idx].mul_mark + seg[idx].add_mark * left_len) % MOD;
    seg[LEFT(idx)].add_mark = (seg[LEFT(idx)].add_mark * seg[idx].mul_mark + seg[idx].add_mark) % MOD;
    seg[LEFT(idx)].mul_mark = (seg[LEFT(idx)].mul_mark * seg[idx].mul_mark) % MOD;

    // Apply to right child
    seg[RIGHT(idx)].total = (seg[RIGHT(idx)].total * seg[idx].mul_mark + seg[idx].add_mark * right_len) % MOD;
    seg[RIGHT(idx)].add_mark = (seg[RIGHT(idx)].add_mark * seg[idx].mul_mark + seg[idx].add_mark) % MOD;
    seg[RIGHT(idx)].mul_mark = (seg[RIGHT(idx)].mul_mark * seg[idx].mul_mark) % MOD;

    // Reset current node marks
    seg[idx].add_mark = 0;
    seg[idx].mul_mark = 1;
}

void multiply_update(int idx, int lo, int hi, int ul, int ur, long long k) {
    if (ul > hi || ur < lo) return;
    if (ul <= lo && hi <= ur) {
        seg[idx].total = (seg[idx].total * k) % MOD;
        seg[idx].add_mark = (seg[idx].add_mark * k) % MOD;
        seg[idx].mul_mark = (seg[idx].mul_mark * k) % MOD;
        return;
    }
    propagate(idx, lo, hi);
    int mid = (lo + hi) / 2;
    multiply_update(LEFT(idx), lo, mid, ul, ur, k);
    multiply_update(RIGHT(idx), mid + 1, hi, ul, ur, k);
    seg[idx].total = (seg[LEFT(idx)].total + seg[RIGHT(idx)].total) % MOD;
}

void addition_update(int idx, int lo, int hi, int al, int ar, long long k) {
    if (al > hi || ar < lo) return;
    if (al <= lo && hi <= ar) {
        seg[idx].total = (seg[idx].total + k * (hi - lo + 1)) % MOD;
        seg[idx].add_mark = (seg[idx].add_mark + k) % MOD;
        return;
    }
    propagate(idx, lo, hi);
    int mid = (lo + hi) / 2;
    addition_update(LEFT(idx), lo, mid, al, ar, k);
    addition_update(RIGHT(idx), mid + 1, hi, al, ar, k);
    seg[idx].total = (seg[LEFT(idx)].total + seg[RIGHT(idx)].total) % MOD;
}

Handling Assignment and Addition Conflicts

When mixing range assignment (cover) with range addition, assignment takes absolute priority. If an asignment occurs, any pending addition marks must be cleared. Conversely, if an addition occurs while an assignment mark exists, the addition should simply modify the assignment value rather than creating a separate addition mark.

Implementation

const long long NULL_VAL = -1;

struct CoverNode {
    long long max_val;
    long long cover_mark; // -1 means no cover
    long long add_mark;
} data[4 * MAX];

void init_node(int idx, int lo, int hi) {
    data[idx].cover_mark = NULL_VAL;
    data[idx].add_mark = 0;
    if (lo == hi) {
        data[idx].max_val = arr[lo];
        return;
    }
    int mid = (lo + hi) / 2;
    init_node(LEFT(idx), lo, mid);
    init_node(RIGHT(idx), mid + 1, hi);
    data[idx].max_val = max(data[LEFT(idx)].max_val, data[RIGHT(idx)].max_val);
}

void push_layer(int idx, int lo, int hi) {
    int mid = (lo + hi) / 2;
    
    if (data[idx].cover_mark != NULL_VAL) {
        // Assignment overrides everything
        data[LEFT(idx)].max_val = data[idx].cover_mark;
        data[LEFT(idx)].cover_mark = data[idx].cover_mark;
        data[LEFT(idx)].add_mark = 0;

        data[RIGHT(idx)].max_val = data[idx].cover_mark;
        data[RIGHT(idx)].cover_mark = data[idx].cover_mark;
        data[RIGHT(idx)].add_mark = 0;

        data[idx].cover_mark = NULL_VAL;
    } else if (data[idx].add_mark != 0) {
        // Apply addition
        data[LEFT(idx)].max_val += data[idx].add_mark;
        if (data[LEFT(idx)].cover_mark != NULL_VAL) {
            data[LEFT(idx)].cover_mark += data[idx].add_mark;
        } else {
            data[LEFT(idx)].add_mark += data[idx].add_mark;
        }

        data[RIGHT(idx)].max_val += data[idx].add_mark;
        if (data[RIGHT(idx)].cover_mark != NULL_VAL) {
            data[RIGHT(idx)].cover_mark += data[idx].add_mark;
        } else {
            data[RIGHT(idx)].add_mark += data[idx].add_mark;
        }

        data[idx].add_mark = 0;
    }
}

void cover_update(int idx, int lo, int hi, int cl, int cr, long long val) {
    if (cl > hi || cr < lo) return;
    if (cl <= lo && hi <= cr) {
        data[idx].max_val = val;
        data[idx].cover_mark = val;
        data[idx].add_mark = 0;
        return;
    }
    push_layer(idx, lo, hi);
    int mid = (lo + hi) / 2;
    cover_update(LEFT(idx), lo, mid, cl, cr, val);
    cover_update(RIGHT(idx), mid + 1, hi, cl, cr, val);
    data[idx].max_val = max(data[LEFT(idx)].max_val, data[RIGHT(idx)].max_val);
}

Complex Merging and Interval Logic

The third categoyr involves problems where merging two intervals is non-trivial. The result often depends on the "boundary" or the connection point between two segments. This requires storing auxiliary information like prefix/suffix states. A classic example is finding the longest alternating subsequence in a dynamic array.

Implementation

struct MergeNode {
    int left_char, right_char;
    int prefix_len, suffix_len, best_len;
} state[4 * MAX];

void merge_up(int idx, int lo, int hi) {
    int mid = (lo + hi) / 2;
    int len_left = mid - lo + 1;
    int len_right = hi - mid;

    MergeNode &cur = state[idx];
    MergeNode &l = state[LEFT(idx)];
    MergeNode &r = state[RIGHT(idx)];

    cur.left_char = l.left_char;
    cur.right_char = r.right_char;
    cur.best_len = max(l.best_len, r.best_len);
    cur.prefix_len = l.prefix_len;
    cur.suffix_len = r.suffix_len;

    if (l.right_char != r.left_char) {
        // Can connect
        cur.best_len = max(cur.best_len, l.suffix_len + r.prefix_len);
        
        if (l.prefix_len == len_left) {
            cur.prefix_len = len_left + r.prefix_len;
        }
        if (r.suffix_len == len_right) {
            cur.suffix_len = len_right + l.suffix_len;
        }
    }
}

void build_alt(int idx, int lo, int hi) {
    if (lo == hi) {
        state[idx].left_char = state[idx].right_char = arr[lo];
        state[idx].prefix_len = state[idx].suffix_len = state[idx].best_len = 1;
        return;
    }
    int mid = (lo + hi) / 2;
    build_alt(LEFT(idx), lo, mid);
    build_alt(RIGHT(idx), mid + 1, hi);
    merge_up(idx, lo, hi);
}

void point_modify(int idx, int lo, int hi, int pos) {
    if (lo == hi) {
        state[idx].left_char ^= 1;
        state[idx].right_char ^= 1;
        return;
    }
    int mid = (lo + hi) / 2;
    if (pos <= mid) point_modify(LEFT(idx), lo, mid, pos);
    else point_modify(RIGHT(idx), mid + 1, hi, pos);
    merge_up(idx, lo, hi);
}