After this lesson, you will be able to: Use segment trees and Fenwick (binary indexed) trees to answer range queries and apply point updates in O(log n), the structures that make 'sum/min/max over a range, with updates' fast.
Suppose you have an array and you need to repeatedly ask 'what is the sum (or min, or max) between index i and index j?' while also updating individual elements. A plain array makes the query O(n); precomputing prefix sums makes the query O(1) but breaks on updates. Segment trees and Fenwick trees give you both: O(log n) queries and O(log n) updates. They are staples of competitive programming and show up in real systems wherever you need fast aggregate-over-a-range with mutation (leaderboards, time-series rollups, range rate-limiting).
Three ways to answer 'sum of elements from i to j': (1) a plain loop, O(n) per query, fine if queries are rare. (2) a prefix-sum array, O(1) per query, but any element update forces an O(n) rebuild, so it fails when the data changes. (3) a segment tree or Fenwick tree, O(log n) for both query and update. The third is what you reach for when you have many queries AND many updates interleaved. The same idea generalizes from sum to any associative operation: min, max, gcd, product.
A segment tree is a binary tree where each node stores the aggregate (say, the sum) of a contiguous range of the array. The root covers the whole array; each child covers half; leaves cover single elements. A range query walks down from the root, combining the O(log n) nodes whose ranges tile the query interval. A point update changes one leaf and the O(log n) ancestors above it. Segment trees are the more flexible option: they handle min/max/gcd, and with 'lazy propagation' they support range updates (add 5 to everything from i to j) too, which Fenwick trees cannot do cleanly.
The Fenwick tree is smaller and simpler than a segment tree when you only need sums. The trick is using the lowest set bit to jump between responsible ranges.
class Fenwick:def __init__(self, n):self.tree = [0] * (n + 1) # 1-indexeddef update(self, i, delta): # add delta at position i (1-indexed)while i < len(self.tree):self.tree[i] += deltai += i & (-i) # move to the next range that includes idef prefix_sum(self, i): # sum of [1..i]total = 0while i > 0:total += self.tree[i]i -= i & (-i) # strip the lowest set bitreturn totaldef range_sum(self, lo, hi): # sum of [lo..hi]return self.prefix_sum(hi) - self.prefix_sum(lo - 1)# Both update and query are O(log n). `i & (-i)` isolates the lowest set bit,# which is the size of the range each node is responsible for.
Use a Fenwick tree when you only need prefix/range sums (or another invertible operation) with point updates: it is shorter to write, uses less memory, and has tiny constants. Use a segment tree when you need min/max/gcd (non-invertible operations a Fenwick tree cannot do), or when you need range updates with lazy propagation. In an interview, mentioning that you would pick the Fenwick tree for a sum-only problem and a segment tree for min/max shows you understand the tradeoff, not just the code.
Reaching for a segment tree when prefix sums (no updates) would do; do not over-engineer. Off-by-one errors from mixing 0-indexed input with the Fenwick tree's 1-indexed array; pick a convention and stick to it. Trying to do range MIN/MAX with a Fenwick tree built for sums; that needs a segment tree (min is not invertible, so you cannot subtract prefixes). Forgetting lazy propagation and doing range updates one element at a time, which is back to O(n) per update. Building the structure on data that never changes, where a precomputed prefix-sum array is simpler and faster.
Pick the best fit.
Sign in and purchase access to unlock this lesson.