Segment Tree Patterns & Practice

Build a segment tree where each node stores the sum of all elements in its range. A leaf stores a single element’s value. A parent stores left_child + right_child.

For update(i, val): start at the root and walk down to the leaf at index i (go left if i is in the left half, right otherwise). Set the leaf to val. On the way back up, recalculate each ancestor: tree[node] = tree[left] + tree[right].

For query(l, r): at each node, check three cases. No overlap (node range entirely outside [l,r]) → return 0. Total overlap (node range entirely inside [l,r]) → return stored sum. Partial overlap → recurse into both children and add results.

Only two things change. The merge function becomes min(left, right) instead of left + right. And the “no overlap” base case returns ∞ (e.g., INT_MAX) instead of 0, because min(anything, ∞) = anything.

Identical to the sum version — change the leaf, then recalculate each parent as min(tree[2*v], tree[2*v+1]) instead of summing.

This same swap works for any associative function: max, GCD, AND, OR, XOR. The pattern: (1) change the merge, (2) change the identity element. The tree structure and recursion stay the same.

In the constructor, build a standard sum segment tree from the input array. Allocate 4*n space for the tree array.

LeetCode’s update(index, val) sets the value (not adds). Walk to the leaf, set it to val, then recalculate ancestors. If your template uses “add delta,” compute delta = val - old_value first.

LeetCode uses 0-based indexing. Make sure your tree’s build(0, n-1) and query/update ranges match. Off-by-one errors are the #1 source of WA.

XOR is associative and commutative. Its identity element is 0 (a⊕0 = a). So it plugs into a segment tree exactly like sum does: merge = XOR, identity = 0.

Each node stores the XOR of all elements in its range. Build, update, and query are identical to the sum template with + replaced by ^.

Without updates, a prefix XOR array works: pre[i] = a[0]^a[1]^...^a[i]. Then xor(l,r) = pre[r] ^ pre[l-1]. The seg tree is better when you also have point updates.

Since queries are point queries (single index), you only walk root-to-leaf. You just need to accumulate lazy tags along the path. No merging children for range results.

For range add [l,r,d]: standard lazy range update (total overlap → add to node + set lazy, partial → push down then recurse). For point query at i: walk root to leaf, pushing down lazy tags at each level. The leaf value is the answer.

A Fenwick tree (BIT) with the range-update-point-query trick works: bit_add(l, d); bit_add(r+1, -d) and point query = bit_prefix_sum(i). But implementing the lazy seg tree is great practice for harder problems.

You need two lazy fields per node: set_val (pending assignment) and add_val (pending addition). Use a boolean has_set to tell if a set is pending (since the set value could be 0).

New set arrives: it overwrites everything — clear any existing add tag. New add at a node with a pending set: the add modifies the set value (set_val += add_delta). Add at a node with only an add: they sum up.

Apply set first (if pending): child.value = set_val × child_range_size, clear child’s add. Then apply add: child.value += add_val × child_range_size. Always clear the parent’s tags after pushing.

For “set to v”: tree[node] = v × range_size (every element becomes v, sum = v × count). For “add d”: tree[node] += d × range_size (each element increases by d).

If l ≤ r, normal range [l, r]. If l > r (wraps around), split into two operations: [l, n−1] and [0, r]. Apply both and combine results (min of both for queries, update both for modifications).

When you add d to every element in a range, the minimum shifts by exactly d. So: tree[node] += d (no × range_size!), lazy[node] += d. Merge: min(left, right).

tree[child] += lazy[parent], lazy[child] += lazy[parent], lazy[parent] = 0. Identity for no-overlap: LLONG_MAX.

XOR-ing every element by v doesn’t give a simple formula for the new sum. Example: XOR-ing [3, 5] by 1 gives [2, 4] — sum went from 8 to 6. There’s no “sum += f(v, range_size)” formula.

Handle each of the 20 bit positions independently. For bit k, maintain a segment tree where each node stores the count of elements that have bit k set. The total sum = Σ count[k] × 2^k.

XOR-ing by v: for each bit k where v has a 1, flip the count: count = range_size − count. Elements that had the bit now don’t, and vice versa. Use a lazy tag (0 or 1) to track pending flips.

Build 20 segment trees (or one tree with 20-element nodes). For sum query on [l,r]: query each bit tree and compute Σ count × 2^k. For XOR update with v: for each bit set in v, do a range flip on that bit tree.

We need elements to the right that are smaller. If we scan from right to left, every element we’ve already processed is to the right of the current one. So the question becomes: “of the values I’ve seen so far, how many are less than the current value?”

Instead of a tree on array indices, build a tree on the value range. Position v in the tree means “how many times value v has appeared so far.” To count values less than x, query sum(0, x−1). To record seeing value x, do update(x, +1).

If values can be up to 10⁹, we can’t create an array of size 10⁹. Coordinate compression solves this: collect all values that actually appear, sort them, and assign each a small index. Example: values [100, −5, 999, 100] → unique sorted: [−5, 100, 999] → mapped to [0, 1, 2]. Now −5 is index 0, 100 is index 1, 999 is index 2. The tree only needs size 3 instead of 10⁹. Relative order is preserved, so “smaller than” queries still work.

(1) Coordinate compress all values. (2) Create a sum segment tree of size = number of unique values, initialized to all zeros. (3) Traverse the array right-to-left. For element with compressed index v: answer[i] = query(0, v−1), then update(v, +1).

Process left to right. At index j, ask: “how many previously-inserted values are > 2×nums[j]?” This is a “count values in a range” query on the value-based segment tree.

You query about 2*nums[j] but insert nums[i]. Your compressed set must include both the original values and the doubled values. Collect all nums[i] and all 2*nums[j] together, sort, deduplicate, map to 0..k−1.

For each j: let c = compressed index of 2*nums[j]. Query sum(c+1, max_index) to count values > 2×nums[j]. Then let v = compressed index of nums[j], do update(v, +1).

Salaries up to 10⁹ — too big for an array. But at most ~4×10⁵ distinct values matter (initial + update + query values). Read all input first, collect every salary value and query bound, sort, deduplicate, map to 0..k−1. Build the tree on this compressed range.

Position c = “how many employees currently have salary with compressed index c.” Initialize by iterating over starting salaries and doing update(compress(salary), +1) for each.

Salary change (old → new): update(compress(old), −1) then update(compress(new), +1). Query “how many in [a,b]”: query(compress(a), compress(b)). Use lower_bound to find compressed indices for query bounds.

Sort by left ascending. Same left? Sort by right descending (wider range first — it might contain narrower ones with the same start).

After sorting, range A at position i contains range B at position j > i if A.right ≥ B.right (A.left ≤ B.left is guaranteed by sort). Process in order: for each range, “how many right endpoints already in the tree are ≤ my right?” = query(0, compress(right_i)). Then update(compress(right_i), +1).

Reverse: process in reverse sorted order. For each range, “how many right endpoints already in the tree are ≥ my right?” = query(compress(right_i), max_index). That gives the count of ranges that contain the current one.

Right endpoints can be large, so coordinate compress them. The segment tree is on compressed right values with point updates and range sum queries.

The maximum subarray might span the boundary between two children. Knowing each child’s best subarray isn’t enough — you need the best suffix of the left child and best prefix of the right child to find cross-boundary subarrays.

Each node stores: total (sum of range), prefix (max prefix sum), suffix (max suffix sum), best (max subarray sum). A leaf with value a: all four = a (or max(0, a) if empty subarrays count as 0).

total = L.total + R.total
prefix = max(L.prefix, L.total + R.prefix)
suffix = max(R.suffix, R.total + L.suffix)
best = max(L.best, R.best, L.suffix + R.prefix)
The last line catches subarrays that cross the midpoint.

After greedily matching brackets in a range, store open = unmatched ( count, close = unmatched ) count. The matched count = total_chars − open − close.

Unmatched ( from the left can match unmatched ) from the right. matched = min(L.open, R.close). Then: open = L.open + R.open − matched, close = L.close + R.close − matched.

For query [l, r] with length len: answer = len − result.open − result.close. This counts characters that are part of matched pairs.

Store {gcd, count} where gcd = GCD of range, count = elements equal to the gcd. Only these are guaranteed to divide every element in the range.

Compute g = gcd(L.gcd, R.gcd). If g == L.gcd, inherit L’s count. If g == R.gcd, inherit R’s count. If g equals both, add counts. If g is smaller than both, count = 0.

Query [l, r] returns {gcd, count}. Ants that leave = (r − l + 1) − count. The staying ants are those whose strength equals the range GCD.

f(x)=a₁x+b₁ and g(x)=a₂x+b₂. Then f(g(x)) = a₁(a₂x+b₂)+b₁ = (a₁·a₂)x + (a₁·b₂+b₁). Store each node as the pair (a, b).

f(g(x)) ≠ g(f(x)) in general. Your merge must apply left-child first, then right-child consistently. Be careful in build, update, AND query to maintain left-to-right order.

Identity function: (a=1, b=0) since f(x) = 1·x + 0 = x. Return this for no-overlap cases. All arithmetic is mod 998244353 — cast to long long before multiplying.

A persistent tree keeps all previous versions. When you “update,” you create a new root sharing most nodes with the old tree (only the root-to-leaf path is new). Version i = tree after inserting the first i elements.

Coordinate compress values. Process positions 1..n. Version i = version i−1 + a +1 at compressed position of a[i]. Now version[r] − version[l−1] gives the frequency distribution for just [l, r].

Start at roots of version[r] and version[l−1]. At each node, left_count = ver_r.left.count − ver_l1.left.count. If left_count ≥ k, go left. Otherwise k −= left_count, go right. This binary searches the value range.

Sort queries by right endpoint. Sweep the array left to right, maintaining a segment tree. Answer each query when you reach its right boundary.

For each value, track its last seen position. At position i: if a[i] was last at position j, do update(j, −1) then update(i, +1). Each value has exactly one “1” in the tree, at its rightmost occurrence.

After processing up to r, every distinct value in [1, r] has a 1 at its rightmost position. Answer for [l, r] = query(l, r) = count of 1s in that range = distinct values with rightmost occurrence in [l, r].

For each subtree, you need every color’s frequency, then sum colors with max frequency. Brute-force = O(n²). The trick: reuse the heavy child’s data instead of recomputing.

Pick the “heavy child” (largest subtree). Keep its frequency data, don’t clear it. Re-add all elements from light children one by one. Each element is re-added O(log n) times total across the whole tree → O(n log n).

Global cnt[] for color frequencies, max_freq, sum_of_max. Adding color c: cnt[c]++. If cnt[c] > max_freq, update max and reset sum to c. If cnt[c] == max_freq, add c to sum. Removing: reverse the logic.