Skip to main content

Segment Trees and Fenwick Trees for Range Queries

What This Concept Is​

Both segment trees and Fenwick trees (also called binary indexed trees, BITs) solve the same kind of problem: given an array A[0..n-1], support range queries and point or range updates in O(log n) per operation.

Segment tree. A complete binary tree over 4n nodes where each node stores an aggregate (sum, min, max, gcd, ...) of a contiguous array range:

  • leaf i stores A[i]
  • internal node storing range [l, r] stores aggregate(A[l..r])
  • queries descend into overlapping ranges in O(log n)
  • updates at a leaf propagate upward in O(log n)
  • lazy propagation extends this to range updates by storing pending-update tokens on internal nodes and deferring them until queried

The operation must be associative so sub-aggregates can be combined along any splitting of the range. Common choices: sum, min, max, gcd, matrix product, polynomial evaluation. Lazy propagation works when the update is a homomorphism that commutes cleanly with the aggregate (e.g., "add c to every element" on a sum tree, "assign c to every element" on a sum or min tree).

Fenwick tree. A much smaller structure (n entries, same size as the array) that supports prefix-sum queries and point updates in O(log n) using the low-bit trick i & -i to walk up and down a virtual tree on index bits. Each index i is responsible for a contiguous range of length i & -i ending at i; update walks i -> i + (i & -i) upward and prefix_sum walks i -> i - (i & -i) downward.

Segment tree is more flexible (any associative, and with lazy propagation, almost any distributive operation); Fenwick tree is smaller (half the memory, simpler cache behavior) and faster for the restricted sum / invertible-group case. A 2D Fenwick tree supports O(log^2 n) rectangle sums and is the standard choice for 2D analytics.

Why It Matters Here​

Range queries are everywhere:

  • competitive programming (easily 30% of problems use one)
  • database indexes for COUNT, SUM, MIN over ranges (e.g., SQL window functions)
  • analytics engines computing windowed aggregates (time-series, real-time dashboards)
  • games, simulations, and graphics computing collision counts or prefix statistics
  • computational geometry (sweep-line structures for rectangle-union problems, stabbing queries)

They are also the cleanest demonstration of the "build a tree over the array" pattern that recurs in sparse tables, k-d trees, interval trees, wavelet trees, and segment-tree-beats variants used in hard olympiad problems.

Concrete Examples​

Example 1 -- segment tree for range sum. Array A = [2, 1, 5, 3, 4].

                [0..4] sum = 15
               /               \
         [0..2] sum = 8      [3..4] sum = 7
          /       \            /      \
       [0..1]=3  [2..2]=5   [3..3]=3  [4..4]=4
       /     \
    [0]=2  [1]=1

query_sum(1, 3) = sum of A[1..3] = 1 + 5 + 3 = 9. The tree descends into [0..2] (partially overlapping) and [3..4] (partially overlapping); it combines [1..1] = 1 + [2..2] = 5 from the left subtree and [3..3] = 3 from the right subtree for total 9.

update(2, +10): set A[2] = 15. Walk from leaf [2..2] upward: [2..2] becomes 15, [0..2] becomes 18, root becomes 25. Three node updates, O(log n) total.

Example 2 -- Fenwick tree for prefix sums. A = [0, 3, 2, -1, 6, 5, 4, -3] (1-indexed), build the BIT.

After processing all updates, bit[1..8] stores:

  • bit[1] = A[1] = 3
  • bit[2] = A[1] + A[2] = 5
  • bit[3] = A[3] = 2
  • bit[4] = A[1..4] = 4
  • bit[5] = A[5] = 6
  • bit[6] = A[5..6] = 11
  • bit[7] = A[7] = 4
  • bit[8] = A[1..8] = 16

prefix_sum(7) walks 7 -> 6 -> 4 -> 0, summing bit[7] + bit[6] + bit[4] = 4 + 11 + 4 = 19 = A[1..7].

update(5, +2) walks 5 -> 6 -> 8, adding +2 to each: bit[5] = 8, bit[6] = 13, bit[8] = 18. Three writes, O(log n) total.

Common Confusion / Misconceptions​

"A segment tree stores the raw values." It stores the aggregate of each range, not the values in duplicate. It is a tree of aggregates layered over the array; the array itself is still accessible but not used during queries. This is why sum and min variants take exactly the same tree shape but different aggregate values.

"Fenwick trees only do prefix sums, so range sum is out of reach." Range sum A[l..r] is computed as prefix_sum(r) - prefix_sum(l - 1). That reduction works for any invertible aggregate (sum, xor, multiplicative group). It does not work for min or max -- those are non-invertible, so use a segment tree.

"Lazy propagation is always necessary for range updates." Only for updates that affect O(range_size) leaves. For point updates, do not add laziness -- it only adds overhead. Decide per-problem whether point or range updates dominate.

"Segment tree memory is exactly 2n." Use 4n as a safe upper bound; the tree may have up to 2 * 2^(ceil(log2 n)) nodes in the array-embedded representation. Undersizing by 2n is a common RTE-causing bug on Codeforces/ICPC.

How To Use It​

Segment tree recipe:

  1. represent the tree in an array of size 4n (safe upper bound) or via explicit nodes
  2. build(node, l, r): recursively build [l..r]
  3. query(node, l, r, ql, qr): return identity if ranges disjoint, node's stored aggregate if fully contained, else recurse into children and combine
  4. update(node, l, r, pos, value): descend to leaf, update, then re-combine upward
  5. for range updates, add a lazy[node] slot; push down before querying a child, apply and re-combine on the way up
  6. verify by running a brute-force oracle (loop over [l..r] computing directly) against the tree on a randomized sequence of 10^5 operations

Fenwick tree recipe:

  1. 1-indexed array bit[1..n]
  2. update(i, delta): while i <= n: bit[i] += delta; i += i & -i
  3. prefix_sum(i): s = 0; while i > 0: s += bit[i]; i -= i & -i; return s
  4. range_sum(l, r) = prefix_sum(r) - prefix_sum(l - 1)
  5. for range update + point query, use a single BIT storing a "difference array"; for range update + range query, use two BITs (the classic trick in Halim/Halim 9.2).

Selection guide:

  • prefix sums, point updates, small memory budget: Fenwick tree
  • arbitrary associative aggregate (min, max, gcd, assignment) with range updates: segment tree with lazy propagation
  • both over a static array where updates are never needed: sparse table (preprocess O(n log n), query O(1) for idempotent ops)
  • offline 2D rectangle queries: 2D Fenwick tree or offline BIT with sweeping

Transfer / Where This Shows Up Later​

  • S5 (OS): kernel accounting counters for per-cpu histograms and interval-scheduler summaries often look like simplified Fenwick trees; tools like bpftrace build range histograms on the same prefix-sum idea.
  • S6 (databases): database indexes for SUM, COUNT, and window aggregates use segment-tree-like accumulators; OLAP cubes precompute aggregates in hierarchical structures analogous to segment trees. Fenwick trees appear in time-series database internals (e.g., M3DB, TimescaleDB continuous aggregates).
  • S7 (architecture): "build an analytics service that answers range-count queries under 10 ms at 10M points" is a classic system-design question; the canonical answer starts with a Fenwick/segment tree over a partitioned array, backed by replicated read paths.
  • S8 (scale): real-time analytics platforms (ClickHouse, Druid, Pinot) use segment-tree-of-segment-trees-style aggregations; sharded Fenwick trees underpin stream counters at Twitter/X and Meta.

Check Yourself​

  1. How much memory does a segment tree over an array of n elements need?
  2. Why can a Fenwick tree handle sum range queries but not min?
  3. What does "lazy propagation" defer, and when is it pushed down?
  4. Which structure would you use for range assignment plus range-max queries?
  5. Explain why i & -i isolates the lowest set bit, and why that gives the correct parent in a Fenwick tree.
  6. Given a problem with 10^5 updates and 10^5 queries, what is the total work for a segment tree? For an O(n) brute-force scan per query? Why does the difference matter?

Mini Drill or Application​

  1. Given A = [1, 3, 5, 7, 9, 11], build a segment tree for range minimum. Draw it.
  2. Run range_min(1, 4) and update(3, 0) on your tree and show the state after each.
  3. Build a Fenwick tree for the prefix-sum of A = [2, 4, 1, 6, 3]. Trace prefix_sum(4) and update(2, +3).
  4. Implement range-add-range-sum using a segment tree with lazy propagation on the array [0, 0, 0, 0, 0], applying add(1, 3, 5) and then range_sum(2, 4).
  5. Implement a Fenwick tree in your language of choice, stress-test it with 10^5 random updates and queries against an O(n) brute-force oracle, and confirm no mismatches.

Read This Only If Stuck​