What Is a Segment Tree?

---

Tree Structure Overview

A segment tree is a binary search tree where each node represents an interval or segment. It allows efficient querying and updating of range-based operations.

Problem Scope

Segment trees excel at handling dynamic range queries and updates, such as finding maximum, minimum, or sum values over intervals. Crucially, they can only maintain information that satisfies the associative property.

Each operation—update or query—has a time complexity of O(log n).

Comparison with Other RMQ Methods

Common solutions for Range Minimum/Maximum Query (RMQ) problems include Sparse Table (ST). Both methods have preprocessing time of O(n log n).

However, unlike ST tables, segment trees support online updates, making them more flexible for dynamic scenarios.

Principles of Segment Trees

---

The name "segment tree" comes from how nodes store segment (interval) enformation. Each internal node splits its interval into two sub-intervals, storing combined results from its children based on associativity.

Core Operations of Segment Trees

---

1. Building the Tree

Building involves three key aspects: what data each node holds, how nodes are indexed, and the construction process.

Consider an array a[1..6] = {1,8,6,4,3,5} with a maximum value segment tree. Red numbers indicate segments, blue ones represent max values within those segments.

Node Data Storage

Leaf nodes correspond directly to array elements. Internal nodes split their intervals evenly, and their stored value reflects the combination of child values (e.g., maximum).

Node Indexing

Nodes follow a complete binary tree indexing scheme. For a parent node i, its left and right children are 2*i and 2*i+1.

Construction Process

Memory allocation should be at least 4*n to avoid runtime errors.

Construction proceeds recursively:

• If l == r, it's a leaf node; assign a[l].
• Otherwise, recursively build left and right subtrees, then combine results.

inline void push_up(int x) {
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
}

inline void build(int l, int r, int x) {
    if(l == r) {
        sum[x] = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    push_up(x);
}

2. Range Queries

Suppose we want to find the maximum in range [2,5]. Not all nodes contain this information directly.

We traverse the tree, selecting relevant intervals that fully cover our target range.

From root down:

• If current node's interval is fully contained in [L,R], return its value.
• Else, recurse into overlapping children.

inline int query(int L, int R, int l, int r, int x) {
    if(L <= l && r <= R) return sum[x];
    int mid = l + r >> 1;
    int ans = 0;
    if(L <= mid) ans += query(L, R, l, mid, x << 1);
    if(R > mid) ans += query(L, R, mid + 1, r, x << 1 | 1);
    return ans;
}

3. Point Updates

Update follows a path from root to the specific index using binary search logic.

Find the target node and propagate changes upward through parents.

4. Range Updates — Lazy Propagation

To handle efficient range modifications, lazy propagation introduces tags to defer updates untill necessary.

When updating a range:

• If the currrent node covers the entire update range, apply change and mark lazy.
• Otherwise, propagate lazy tags before recursing deeper.

Example: Adding 1 to [1,3]:

• At root [1,6], recurse to left subtree [1,3].
• At [1,3], mark lazy tag and update value.
• On recursion back, update parent nodes accordingly.

inline void push_down(int x, int ln, int rn) {
    if(add[x]) {
        add[x << 1] += add[x];
        add[x << 1 | 1] += add[x];
        sum[x << 1] += add[x] * ln;
        sum[x << 1 | 1] += add[x] * rn;
        add[x] = 0;
    }
}

inline void update(int L, int R, int C, int l, int r, int x) {
    if(L <= l && R >= r) {
        sum[x] += C * (r - l + 1);
        add[x] += C;
        return;
    }
    int mid = l + r >> 1;
    push_down(x, mid - l + 1, r - mid);
    if(L <= mid) update(L, R, C, l, mid, x << 1);
    if(R > mid) update(L, R, C, mid + 1, r, x << 1 | 1);
    push_up(x);
}

5. Range Queries with Lazy Tags

Add push_down during traversal for accurate results.

Sample Problems

---

P3372 【Template】Segment Tree 1

Basic implementation covering both range updates and queries.

P1438 Bored Sequence

Direct application not feasible due to varying increments.

Use difference arrays to convert differences into constant additions, enabling standard segment tree usage.

Query becomes prefix sums via normal range sum queries.

P4588 [TJOI2018] Mathematical Calculation

Operations resemble multiplication/division sequences.

Each division effectively removes one factor, each multiplication adds one.

Use segment tree to track product of factors, allowing single-point updates and range products.

P4145 Seven Minutes to God / Kingdom Tour

Square root operations on large numbers eventually stabilize at 1 or 0.

Maintain maximum value in segment tree to skip unnecessary computations.

CF1263E Editor

Bracket matching problem modeled using numeric values:

• Left bracket = +1
• Right bracket = -1
• Other chars = 0

Track prefix sums:

• All prefixes must be ≥ 0
• Final sum must equal 0

Use segment tree to maintain prefix sums and deepest nesting level.

P2894 [USACO08FEB] Hotel G

Supports range assignments and queries for longest continuous free rooms.

Track three values per node:

• Longest free interval
• Longest prefix-free interval
• Longest suffix-free interval

Combine these efficiently during merge operations.

Binary search or recursive search can locate the leftmost valid interval.

SP1043 GSS1 - Can You Answer These Queries I

Classic problem involving maximum subarray sum.

Define structure:

struct Node {
    int val;     // total sum
    int left;    // max prefix sum
    int right;   // max suffix sum
    int middle;  // max subarray sum
};

Merge rules:

• val: sum of left and right values
• left: max of left’s prefix or left sum plus right’s prefix
• right: max of right’s suffix or right sum plus left’s suffix
• middle: max among left’s middle, right’s middle, or cross-sum

GSS3 - Can You Answer These Queries III

Similar to GSS1 but includes point updates.

P1253 Fusu's Problem

Two types of lazy tags: assignment (t1) and addition (t2).

Update functions can be unified by passing type flag.

P3870 [TJOI2009] Switches

Binary state (on/off) management.

Range XOR flips bits; count ones via sum query.

Flip logic: new_sum = (length - old_sum)

P1471 Variance

Compute variance using formula expansion.

Maintain both sum and squared sum.

When adding constant k:

• New sum = old sum + n*k
• New squared sum = old squared sum + 2kold_sum + n*k²

Use segment tree to maintain these quantities.

P1558 Color Board Game