Segment trees and Fenwick trees are data structures used to answer repeated range queries efficiently while values in an array change. They are common in competitive programming, algorithms courses, and performance-sensitive applications. This cheat sheet helps students compare the two structures, remember update and query patterns, and choose the right tool for a problem.
A segment tree stores information about intervals, so it can support operations such as range sum, range minimum, and range maximum in O(log n) time. A Fenwick tree, also called a Binary Indexed Tree, stores partial prefix information and is especially compact for prefix sums and point updates. Lazy propagation extends segment trees so range updates can be delayed and applied only when needed.
Key Facts
- A segment tree for an array of size n answers range queries and point updates in O(log n) time after O(n) construction.
- A standard segment tree usually needs up to 4n storage when implemented with a recursive array representation.
- For a sum segment tree, each internal node stores tree[v] = tree[2v] + tree[2v + 1].
- A Fenwick tree supports prefixSum(i) and add(i, delta) in O(log n) time using index changes based on i & -i.
- In a 1-indexed Fenwick tree, update uses i = i + (i & -i), while prefix query uses i = i - (i & -i).
- A range sum from l to r using prefix sums is rangeSum(l, r) = prefixSum(r) - prefixSum(l - 1).
- Lazy propagation lets a segment tree handle range updates in O(log n) time by storing pending changes in lazy nodes.
- Fenwick trees are simpler and use O(n) memory, but segment trees are more flexible for custom range operations.
Vocabulary
- Segment Tree
- A binary tree data structure where each node stores a value for a specific interval of an array.
- Fenwick Tree
- A compact array-based data structure that stores partial prefix values to support fast prefix queries and updates.
- Range Query
- A request for a computed value, such as a sum or minimum, over a contiguous interval from index l to index r.
- Point Update
- A change made to one array element, often followed by updating stored tree values along a path.
- Lazy Propagation
- A segment tree technique that delays range updates by storing pending changes until a node must be visited.
- Least Significant Bit
- In a Fenwick tree, i & -i gives the value of the lowest set bit of index i and controls jumps between stored ranges.
Common Mistakes to Avoid
- Using 0-index formulas in a 1-indexed Fenwick tree is wrong because i & -i logic assumes positive 1-based indices in the standard version.
- Forgetting to update parent nodes in a segment tree is wrong because every internal node must reflect the combined values of its children.
- Allocating only n cells for a recursive segment tree is wrong because the tree array may need up to 4n cells to avoid index overflow.
- Computing rangeSum(l, r) as prefixSum(r) - prefixSum(l) is wrong because it excludes the value at index l when using inclusive ranges.
- Applying a lazy range update without pushing or storing pending values is wrong because child nodes may later return outdated query results.
Practice Questions
- 1 An array has n = 100000 elements. What is the time complexity of one point update and one range sum query using a segment tree?
- 2 Using prefix sums from a Fenwick tree, if prefixSum(7) = 34 and prefixSum(3) = 12, what is rangeSum(4, 7)?
- 3 In a 1-indexed Fenwick tree, starting at i = 12 during an update, what is the next index visited using i = i + (i & -i)?
- 4 A problem needs frequent range minimum queries and point updates. Explain whether a Fenwick tree or a segment tree is the better choice and why.