Segment Tree and Fenwick Tree

When to use a Fenwick tree or a segment tree

Use a Fenwick tree (binary indexed tree) when you need:

• Range sums (or counts) on an array whose values change, such as a live leaderboard or a running total of sales per hour.
• To count how many items are smaller than a given value as items arrive (counting inversions).
• A structure that is tiny to write: about 15 lines and one array.

Use a segment tree when you need:

• Range minimum, maximum, gcd or any combining operation that is not a plain sum, on an array that changes.
• Range updates, such as "add 5 to every value from position 3 to 9", using lazy propagation.
• Questions such as "the first position where the prefix sum passes X", answered by walking down the tree.

Use something else when:

• The array never changes: use prefix sums for sums (O(1) per query) or a sparse table for min and max (O(1) per query).
• You query one position only: a plain array is enough.
• The data lives in a database: its index already does this.

Do not write your own in production unless you must. Most languages have no built-in version (see the real-world section). In interviews and contests you will write one by hand.

How Fenwick and segment trees work

Both answer the question "what is the combined value of this range?" in O(log n) and apply a change in O(log n). A plain array makes one of those fast and the other slow. A prefix sum array answers a range in O(1) but a change rewrites up to n cells. A plain array applies a change in O(1) but a range costs O(n).

Both trees split the difference by storing partial sums that cover ranges of different sizes:

A tree stores sums of ranges whose sizes are powers of two, so any range is the union of about log n of them, and any one change touches only about log n of them.

• A Fenwick tree keeps one array. Cell i holds the sum of the last lowbit(i) positions ending at i, where lowbit(i) is the lowest set bit of i (i & -i). For example cell 4 covers positions 1 to 4, and cell 6 covers positions 5 to 6.

  Here is lowbit for the eight cells in this lesson. The lowest set bit is the rightmost 1 in the binary form.

  Cell	Binary	lowbit	Positions covered
  1	001	1	1
  2	010	2	1 to 2
  3	011	1	3
  4	100	4	1 to 4
  5	101	1	5
  6	110	2	5 to 6
  7	111	1	7
  8	1000	8	1 to 8

  To sum positions 1 to 7, write 7 as 111. Take cell 7 (covers 7), remove the lowest bit to get 110 = 6 (covers 5 to 6), remove it again to get 100 = 4 (covers 1 to 4), then 000 = 0 stops. The cells are 7, 6 and 4, and together they cover positions 1 to 7 exactly once.

• A segment tree keeps a binary tree. Each leaf is one value. Each parent stores the combined value of its two children, so the root covers everything. In the usual array layout, the children of node i are 2i and 2i + 1. The version in the simulation is the bottom-up layout: for n values the leaves sit at cells n to 2n - 1 (value number p, counting from 0, is at cell n + p), the internal nodes are cells 1 to n - 1, and the array has 2n cells. The simpler top-down recursive version needs up to 4n cells when n is not a power of two, which is why you will see both "2n" and "4n" quoted.

Try it

Choose a structure and an operation sequence. The array has eight values, positions 1 to 8.

Things to try:

• Run the Prefix sum array with Only the query. It touches 2 cells, the cheapest of the three. Then choose Add 5 to position 3, then the same query: the update rewrites 6 cells (positions 3 to 8), 8 cells in all.
• Run the Fenwick tree with the same two operations. The update touches 3 cells (3, then 4, then 8) and the query 4 cells, 7 in all. With only 8 values the saving is small. The prefix array's update cost grows with n, while the Fenwick tree's grows with log n.
• Run the Segment tree and watch the update climb from the leaf to the root, one cell per level (4 cells), then the query pick a few whole segments (4 more).

Fenwick and segment tree operations: update, prefix and range

Fenwick update at position i by delta. Add delta to cell i, then move to i + lowbit(i) and repeat while i is within the array.

Fenwick prefix sum of positions 1 to i. Add cell i, then move to i - lowbit(i) and repeat while i is above 0.

Fenwick range sum l to r. Compute prefix(r) - prefix(l - 1). This only works because sums can be subtracted.

Segment tree update. Change the leaf, then walk up to the root, recomputing each parent from its two children.

Segment tree range query. Start with the two ends of the range at the leaf level. At each level, if the left end is a right child, include that node and move right; if the right end is a right child, step left and include that node; then move both ends up one level. Only whole segments are added, never single values.

In pseudocode, for the half-open range [l, r) (it includes l and stops before r), with 0-based values:

query(l, r):
    l = l + n
    r = r + n
    result = identity            # 0 for sum
    while l < r:
        if l is odd:  result = combine(result, t[l]); l = l + 1
        if r is odd:  r = r - 1; result = combine(result, t[r])
        l = l / 2
        r = r / 2
    return result

Worked query. Take the values after the update in the simulation: 3 2 10 1 4 6 2 8, so n = 8 and value number p is at cell 8 + p. We want positions 2 to 7, which are values number 1 to 6, so the half-open range is [1, 7).

1. l = 9, r = 15. l is odd: add cell 9 (value 2), l = 10. r is odd: r = 14, add cell 14 (value 2). Halve: l = 5, r = 7.
2. l = 5 is odd: add cell 5, which is cell 10 + cell 11 = 10 + 1 = 11, then l = 6. r = 7 is odd: r = 6, add cell 6, which is cell 12 + cell 13 = 4 + 6 = 10. Halve: l = 3, r = 3.
3. l is no longer below r, so stop. The total is 2 + 2 + 11 + 10 = 25, the same answer as the Fenwick tree, using four whole segments.

Because the two ends are combined in the order they are met, the bottom-up query is only correct for operations where order does not matter (commutative ones such as sum, min, max and gcd). For an order-sensitive operation, such as joining strings, keep a separate left result and right result.

Lazy propagation (range update). Suppose we must add 5 to every value in positions 3 to 9, and there may be thousands of positions. Changing every leaf costs O(n). Instead, find the few whole nodes that cover the range, as in a query. For each such node, add 5 × (number of positions it covers) to its stored sum, and write a tag on it that says "5 is still owed to every position below you". Nothing below is touched yet. Then recompute the ancestors of those nodes on the way up.

Later, a query or update needs to look inside a tagged node. Before going down, do a push-down: add the tag to each child (child sum grows by 5 × its size, and the child gets or adds to its own tag), then clear the parent's tag. Now the children are correct and the work moves down only one level at a time, along one path. Each range update and each range query still touches O(log n) nodes. The cost is one extra array for the tags and care with the order: always push down before you read or change a child.

A plain sum Fenwick tree cannot do range minimum or maximum, because you cannot subtract a minimum. This is the interview fact, and it is the main reason to choose a segment tree. The wording matters: a Fenwick tree can answer a prefix maximum if values only ever increase, but an arbitrary range minimum or maximum with changing values needs a segment tree.

Dry run: update and prefix on the Fenwick tree

Start with the values 3 2 5 1 4 6 2 8 from the simulation. After building, the Fenwick cells 1 to 8 are 3 5 5 11 4 10 2 31. For example cell 4 = 3 + 2 + 5 + 1 = 11, and cell 6 = 4 + 6 = 10.

update(3, +5). Start at 3. Cell 3 becomes 5 + 5 = 10. Then 3 + lowbit(3) = 3 + 1 = 4. Cell 4 becomes 11 + 5 = 16. Then 4 + 4 = 8. Cell 8 becomes 31 + 5 = 36. Then 8 + 8 = 16, which is past the end, so stop. Three cells changed: 3, 4 and 8. The cells are now 3 5 10 16 4 10 2 36.

prefix(7). Start at 7. Add cell 7 = 2. Then 7 - 1 = 6. Add cell 6 = 10. Then 6 - 2 = 4. Add cell 4 = 16. Then 4 - 4 = 0, so stop. The total is 2 + 10 + 16 = 28.

Range sum of positions 2 to 7, before and after. The range is prefix(7) - prefix(1). Before the update: prefix(7) = 2 + 10 + 11 = 23 and prefix(1) = 3, so the answer is 20. After the update: prefix(7) = 28 and prefix(1) is still 3, so the answer is 25. Position 3 is inside the range, so the answer grows by exactly 5.

Edge cases and pitfalls

• Position 0 in a Fenwick tree. lowbit(0) is 0, so add(0, x) never moves forward and loops forever. Use positions 1 to n, or shift 0-based input by one.
• Empty prefix. prefix(0) is 0 and the loop does not run. That is why range_sum(1, r) works with prefix(l - 1) = prefix(0).
• Negative values and deltas. Sums handle them fine. Prefix sums are not monotonic any more, so do not use "walk down while the sum is below X" unless all values are non-negative.
• Overflow. Many additions can pass the range of a 32-bit integer. Use 64-bit integers, as the sample code does.
• Update means delta. A Fenwick update adds a difference. To set a position to a new value, add new - old, so you need the old value stored somewhere.
• Size not a power of two. Both trees work for any n. The Fenwick update stops when the index passes n. The bottom-up segment tree works for any n with 2n cells, though the shape of the tree is uneven. The recursive version needs up to 4n cells.
• Off-by-one ranges. Decide once whether your range is inclusive or half-open, and write it in the function name or a comment.
• Lazy tags. Forgetting to push down before reading a child gives stale answers that look almost right.
• One position or one value. A tree of size 1 is fine: the segment tree has just the leaf at cell 1, and the Fenwick tree has one cell.

Fenwick and segment tree time complexity

n is the number of values.

Build. Adding the n values one at a time with add costs O(n log n), which is what the sample code does. The linear build is a small change: copy the values into the cells, then for each i from 1 to n, add cell i into its parent cell i + lowbit(i) if that cell exists. Each cell is touched once, so it is O(n). The simulation uses the linear build. The segment tree is linear too, because each internal node is computed once from its two children.

Range update with a Fenwick tree. Store the differences between neighbours in one Fenwick tree. Adding v to positions l to r changes only two differences: add v at l and subtract v at r + 1. A range sum then needs a second Fenwick tree that tracks the differences weighted by position, which is why the table says "two trees". A point value is the prefix sum of the differences.

Neither tree beats a prefix array when nothing changes, and neither beats a plain array when you only change values and never query ranges.

Fenwick and segment trees vs other structures

n is the array length. The Fenwick tree wins on sums that change, because it is short and fast. The segment tree wins whenever the operation is not a sum, or ranges themselves change.

How to explain Fenwick and segment trees in an interview

• Start from the trade-off: a prefix array has fast queries and slow updates, a plain array the reverse. "Both trees make both operations O(log n)."
• For a Fenwick tree, say what a cell means ("the sum of the last lowbit(i) positions ending at i") and why updates jump forward by lowbit and queries jump backward by it. That is the whole trick.
• For a segment tree, say "each node is the combination of its two children; a range is split into at most 2 log n whole segments".
• Name the limits: a sum Fenwick tree needs an operation you can undo (such as sum), a segment tree handles any combine operation, and offline problems may be easier with sorting and a Fenwick tree.