Range:..

Set:=

Overview & Concept

A Segment Tree is a binary tree used for storing intervals or segments. It allows querying which of the stored segments contain a given point, or performing aggregate associative operations (such as Range Sum, Range Minimum, or Range Maximum) over an arbitrary array range in O(log n) time, while supporting point and range updates with identical logarithmic efficiency.

How It Works

Interval Partitioning: Root represents [0..n-1]. Each node [L..R] divides into left child [L..mid] and right child [mid+1..R].

Leaf Base Cases: Nodes with L == R correspond to individual array elements array[L].

Associative Merging: Internal nodes store the associative combination of their two children (e.g. sum = left.sum + right.sum).

Canonical Decomposition: Any range query [qL..qR] is decomposed into at most 2 disjoint canonical nodes per tree level.

Step-by-Step Execution

1. Divide and Conquer BuildRecursively build left and right subtrees, combining leaf values up to root in O(n) total time.

2. Range Overlap EvaluationClassify node interval against query: Disjoint (prune), Total Overlap (return sum), or Partial (recurse).

3. Result AggregationSum results from left and right child queries and return total.

4. Point UpdateTraverse down to leaf, modify element, and recompute ancestor sums back up to root.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(log n) queries & updates	O(log n)	O(log n) bounded by 4 log n node visits	O(n) bounded by 4n buffer
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

// Segment Tree (Range Sum Query & Point Update)
operation build(node, l, r):
  if l == r: tree[node] = arr[l]; return
  mid = (l + r) / 2
  build(2*node, l, mid); build(2*node+1, mid+1, r)
  tree[node] = tree[2*node] + tree[2*node+1]

operation query(node, l, r, ql, qr):
  if r < ql or l > qr: return 0 // Disjoint
  if ql <= l and r <= qr: return tree[node] // Total overlap
  mid = (l + r) / 2
  return query(2*node, l, mid, ql, qr) + query(2*node+1, mid+1, r, ql, qr)

operation update(node, l, r, idx, val):
  if l == r: tree[node] = val; arr[idx] = val; return
  mid = (l + r) / 2
  if idx <= mid: update(2*node, l, mid, idx, val)
  else: update(2*node+1, mid+1, r, idx, val)
  tree[node] = tree[2*node] + tree[2*node+1]

Algorithmic Invariants

Range Partition Invariant: For every internal node [L..R], left.R + 1 == right.L and left.L == L and right.R == R.
Canonical Covering Invariant: Any contiguous range [qL..qR] is covered by a unique minimal set of disjoint segment tree nodes.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Versatile: supports any associative operation (Sum, Min, Max, GCD, Matrix Multiplication).
•Guaranteed O(log n) query and update latency.
•Extensible to lazy propagation for O(log n) range updates.

Trade-offs & Limitations

•Requires up to 4n linear memory buffer.
•Higher constant overhead compared to Fenwick Tree for simple range sums.

Real-World Applications

Geographic Information Systems (GIS)

Window bounding box spatial range queries over map points.

Financial Time Series

Dynamic rolling volatility, max drawdown, and running volume tallies.

Graphics & Ray Tracing

Bounding Volume Hierarchy (BVH) interval intersection tests.

Decision Guide: When to Use

Ideal Scenarios

✓When arrays experience frequent interleaved point/range updates and range queries.
✓When queries involve non-invertible operations like Range Minimum Query (RMQ).

Consider Alternatives When

✕When the array is completely static (use Sparse Table for O(1) RMQ or Prefix Sums for O(1) sums).
✕When only point updates and prefix sums are needed (use Fenwick Tree for simpler 1D buffer).

Compare trade-offs and complexity across complementary tools in AlgoViz.

Fenwick Tree AVL Tree