Segment & Fenwick trees
When a list keeps changing and you keep asking for sums of its ranges, store the sums of its halves, quarters and eighths. Then both a change and a range sum take O(log n).
Prefix sums can't keep up with changes
Prefix sums answer "what is the sum of positions L to R" in O(1), after O(n) preparation. But change one item and every running total after it is wrong: an update costs O(n). When sums and changes are mixed, something in between is needed.
Kept as | Change one item | Sum of a range |
|---|---|---|
The plain list | O(1) | O(n) |
Prefix sums | O(n) | O(1) |
A segment tree or a Fenwick tree | O(log n) | O(log n) |
Both trees store sums of stretches of positions, chosen so that any range is made of a few stored stretches, and any single position belongs to only a few of them.
A segment tree stores the sum of every half, quarter and eighth
A segment tree is a binary tree over the positions of a list. The root holds the sum of everything; its two children hold the sums of the left and right halves; their children split those halves again, down to leaves that hold one item each. Like a heap, it fits in a plain list: node i's children are 2i + 1 and 2i + 2.
With 8 items the tree is perfect and needs 2 × 8 − 1 = 15 cells. For a length that isn't a power of two, round up to the next power of two, p, and use 2p − 1 cells, which is always under 4n; many write 4n to be safe. The code below does the rounding.
A range is a handful of whole nodes
The rule
Any range of positions splits into at most two nodes per level that lie entirely inside it, so a range sum adds O(log n) stored sums. A single position lies in exactly one node per level, so an update recomputes O(log n) sums.
A query starts at the root and asks each node one question. Entirely outside the range: it adds 0. Entirely inside: its stored sum is used as it is, without looking deeper. Partly inside: ask both children. An update walks down to the position's leaf, changes it, and recomputes every sum on the way back up.
The same tree works for any way of combining two answers that doesn't care how you group them: minimum, maximum, a product. Only the line that combines the two children changes.
A Fenwick tree packs the same idea into one array
A Fenwick tree, also called a binary indexed tree, keeps n + 1 cells and no explicit tree at all. Number the positions from 1. Cell i holds the sum of a stretch ending at i, whose length is the largest power of two that divides i: cell 6 covers 5 and 6, cell 8 covers 1 to 8, cell 7 covers only 7.
To sum positions 1 to i, add cell i, then jump left past its stretch (i minus that power of two) and repeat until 0. To add to position i, update cell i and jump right by the same amount, to the next cell whose stretch also covers i. Either way, each jump clears or carries one binary digit of i, so there are O(log n) of them. Real code computes the lowest set bit in one step as i & −i (Bit manipulation); the walkthrough's loop is only for readability, and makes each step O(log n) instead of O(1). A range L to R is then the sum up to R minus the sum up to L − 1.
The walkthrough uses a Fenwick tree for counting rather than summing values: walking from the right, position v counts how many times value v has been seen, so the sum of positions 1 to x − 1 is the number of smaller values already seen to the right of x.
Values that are large or negative don't fit as positions directly. Replace each by its rank in sorted order first; the counts don't change.
Fenwick for sums, segment tree for everything else
Fenwick tree | Segment tree | |
|---|---|---|
Memory | n + 1 cells | 2n to 4n cells |
Code | A few lines | Recursive, longer |
Combines | Sums and counts (anything that can be undone by subtraction) | Sums, minimum, maximum and more |
Change a whole range at once | Only with extra tricks | Yes, by postponing the work to the nodes below until a query needs it |
If the list never changes, neither tree is needed: prefix sums are simpler and faster.
4 questions
Remember this
- Prefix sums give O(1) range sums but O(n) updates; segment and Fenwick trees give O(log n) for both.
- A segment tree stores the sum of every half, quarter and eighth; a query adds a few whole nodes, an update fixes one path.
- A segment tree combines children with any grouping-insensitive operation: sum, minimum, maximum.
- A Fenwick tree keeps n + 1 cells; cell i covers the stretch ending at i whose length is the largest power of two dividing i.
- Counting with a Fenwick tree over values answers "how many smaller so far" in O(log n).
Now solve some yourself
Only this topic 0 of 8 solved
- MediumTeams of three with strictly rising or falling ratings
- MediumRange sums while values change
- MediumAlternate OR and XOR up a tree as values change
- HardCost of inserting into a sorted list one by one
- HardFirst hotel with enough rooms for each group
- HardFlip ranges and count multiples of three
- HardTriplets in the same order in two lists
- HardHeights of a stack of falling squares
Mixed with topics you have practiced 0 unlocked
6 more once you have practiced Merge sort & quicksort, Prefix sums, Merge intervals, Dynamic programming: basics, Linear & binary search. Play one of its examples to the end and solve one of its problems to unlock them.
Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.
Next