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.
Understanding Segment Tree & Fenwick Tree Reference
A segment tree works by breaking an array into nested intervals. The root represents the whole array. Each lower node represents a smaller part, until leaf nodes represent single positions.
To answer a query from one position to another, the algorithm selects a small set of nodes whose intervals fit together exactly across that requested region. It does not need to inspect every value. This structure works when the stored result can be combined from two smaller results.
Sums, minimum values, maximum values, greatest common divisors, and counts all fit this pattern. The combine rule must be chosen carefully because it defines what every parent node means.
A Fenwick tree uses a different idea. Each position stores a subtotal for a block ending at that position. The size of that block comes from the lowest set bit in the binary form of the index.
For example, some cells cover one value, some cover two values, and some cover larger power of two blocks. A prefix query moves backward through these blocks until it reaches the start. An update moves forward to every block that includes the changed position.
This explains why Fenwick trees usually use indexing that starts at one. Index zero has no lowest set bit, so the update and query steps would fail to move correctly.
Lazy propagation matters when one instruction changes many consecutive values. Imagine adding five points to every score from student twenty through student eighty. Updating leaves one by one wastes work.
A lazy node records a promise that its whole interval should receive a change. The tree can keep that promise at a higher node until a later query needs information from one of its children. At that moment, the pending change is pushed downward.
Students often make mistakes by updating a node value but forgetting its lazy tag, or by pushing a tag without clearing it afterward. Range addition and range assignment need different tags. Assignment can replace an earlier value, while addition accumulates with earlier additions.
These structures appear in live scoreboards, game leaderboards, sensor readings, financial totals, and image processing tasks where many values change over time. The hardest part is usually not writing the tree loops. It is defining interval boundaries and checking what each node stores.
Decide early whether ranges include both endpoints. Keep that choice identical in every function. Test a tiny array by hand, including a range of one element, the full range, the first position, and the last position.
For sums, use a numeric type large enough for repeated additions. For minimum or maximum queries, choose a correct neutral value for an empty part of a query. Clear definitions prevent most bugs before performance becomes important.