Fenwick Tree (Binary Indexed Tree)

Competitive-programming territory

Fenwick trees (also called Binary Indexed Trees, or BITs) are a CP staple for exactly the same problems the previous lesson’s segment tree solves — just with roughly a third of the code, at the cost of only working for invertible operations like sum or xor (not min/max).

A Fenwick tree answers “prefix sum up to index i” and “add delta at index i” in $O(\log n)$ each, using one flat array and a single bitwise trick — no recursion, no explicit tree nodes, and about fifteen lines of code.

What you’ll learn

• The lowbit trick, i & (-i), and why it isolates the lowest set bit of i.
• How that one trick gives $O(\log n)$ point update and $O(\log n)$ prefix-sum query.
• Getting an arbitrary range sum from two prefix queries.
• Why a Fenwick tree is simpler but less general than a segment tree, and when to reach for which.
• A brief look at extending it to 2D.

The cue

You are looking at a Fenwick tree when…

• The array is mutated between queries, and each query wants a prefix sum or a range sum. A static array wants a plain prefix-sum array — $O(1)$ per query, and a Fenwick tree would be strictly worse.
• The operation combining elements is invertible: sum, XOR, count, product over a field. Range sum comes from prefix(r) - prefix(l-1), and that subtraction is what the structure relies on.
• The problem is “count how many earlier elements are smaller/greater” — inversions, “count of smaller numbers after self”, reverse pairs. These are Fenwick problems in disguise: index the tree by value, not by position, and query a prefix of the value range.
• Constraints are around $10^5$–$10^6$ with $10^5$ mixed updates and queries, so $O(n)$ per query is too slow and $O(\log n)$ is expected.

The reframe: tree[i] does not store element i. It stores the sum of the lowbit(i) elements ending at i — a set of ranges chosen so that any prefix is the union of $O(\log n)$ of them, and any position belongs to $O(\log n)$ of them. Update walks up, query walks down, and both walks are driven by i & -i.

Reach for something else when the array is static (prefix-sum array), when the combining operation is not invertible — min, max, gcd — because there is no way to subtract a prefix (segment tree or a sparse table for static min/max), or when you need range assignment/addition over a range rather than point updates, which is lazy propagation’s job.

The lowbit trick: i & (-i)

Every positive integer, in two’s-complement binary, has the property that i & (-i) isolates its lowest set bit — the smallest power of two that divides it:

lowbit.py

def lowbit(i):
    return i & (-i)
 
 
for i in [1, 2, 3, 4, 6, 12, 24]:
    print(f"i={i:>2} ({i:>05b})  lowbit={lowbit(i)}")

text

>>> bin(12)
'0b1100'
>>> lowbit = 12 & (-12)
>>> lowbit
4
>>> bin(lowbit)
'0b100'

Every Fenwick tree index i (the tree is conventionally 1-indexed) is made “responsible” for summing exactly lowbit(i) elements, ending at i itself:

Index i	lowbit(i)	Range it’s responsible for
1	1	[1, 1]
2	2	[1, 2]
3	1	[3, 3]
4	4	[1, 4]
5	1	[5, 5]
6	2	[5, 6]
7	1	[7, 7]
8	8	[1, 8]

Connecting each index i to i + lowbit(i) (the index that will next need to know about a change at i) turns this table into an actual tree:

diagram Fenwick tree structure for n=8 -- edges follow i += lowbit(i), the update-chain jump mermaid

  graph BT
    N1["1: owns [1,1]"] --> N2["2: owns [1,2]"]
    N2 --> N4["4: owns [1,4]"]
    N3["3: owns [3,3]"] --> N4
    N5["5: owns [5,5]"] --> N6["6: owns [5,6]"]
    N6 --> N8["8: owns [1,8]"]
    N7["7: owns [7,7]"] --> N8
    N4 --> N8

Update walks up this tree (i += lowbit(i), toward the root) to touch every ancestor whose range includes i. Query walks down — really, it walks toward 0 (i -= lowbit(i)), accumulating sums from disjoint ranges that together cover [1, i].

sketch Update chain (amber, walks up) vs. prefix-sum chain (blue, walks toward 0) p5.js Pause Restart

update(3) touches 3 -> 4 -> 8. prefix_sum(6) touches 6 -> 4, then stops at 0.

Build, update, and query

fenwick_tree.py

class FenwickTree:
    """1-indexed Binary Indexed Tree: O(log n) point update, O(log n) prefix-sum query."""
 
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)   # tree[0] is unused -- indices are 1..n
 
    def update(self, i, delta):
        """Add `delta` to the value at position i (1-indexed)."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)          # walk UP to the next index this one feeds into
 
    def prefix_sum(self, i):
        """Sum of elements 1..i (1-indexed, inclusive)."""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)          # walk toward 0, one disjoint range at a time
        return total
 
    def range_sum(self, left, right):
        """Sum over the inclusive 1-indexed range [left, right]."""
        return self.prefix_sum(right) - self.prefix_sum(left - 1)
 
    @classmethod
    def from_list(cls, values):
        """Build in O(n log n) via repeated point updates (simple; an O(n) build exists too)."""
        bit = cls(len(values))
        for i, v in enumerate(values, start=1):
            bit.update(i, v)
        return bit
 
 
values = [3, 2, -1, 6, 5, 4, -3, 3]     # conceptually 1-indexed: position 1..8
bit = FenwickTree.from_list(values)
 
print("sum of first 5 elements:", bit.prefix_sum(5))         # 3+2-1+6+5 = 15
print("sum of elements 3..6:", bit.range_sum(3, 6))          # -1+6+5+4 = 14
 
bit.update(3, 10)                                             # position 3: -1 -> 9
print("sum of elements 3..6 after point update:", bit.range_sum(3, 6))   # 9+6+5+4 = 24

range_sum is where the “invertible” requirement shows up: sum(right) - sum(left - 1) only works because subtraction can undo addition. There’s no equivalent trick for min or max — you can’t “subtract” a minimum back out of a combined range — which is exactly why a Fenwick tree can’t replace a segment tree for those operations.

Range update AND range query, together

The BIT above does point update + range query. Flipping it around to range update + range query is possible with a second BIT tracking a difference array, but it takes real care to get right. If a problem needs both range updates and range queries, reach for the segment tree with lazy propagation from the previous lesson instead — it supports that combination natively.

Dry run

values = [3, 2, -1, 6, 5, 4, -3, 3], 1-indexed. After building, tree holds:

i	binary	lowbit(i)	covers positions	value
1	0001	1	1..1	3
2	0010	2	1..2	5
3	0011	1	3..3	−1
4	0100	4	1..4	10
5	0101	1	5..5	5
6	0110	2	5..6	9
7	0111	1	7..7	−3
8	1000	8	1..8	19

The single rule to memorise: tree[i] covers the lowbit(i) positions ending at i — that is, the range (i − lowbit(i), i]. Everything else follows from it. Note that odd indices cover exactly one element, and index 8 covers the whole array, so the structure is neither “one node per element” nor a balanced tree — it is a set of ranges chosen so the bit arithmetic works out.

Query — prefix_sum(7). Walk down, subtracting lowbit each time:

i	reads tree[i]	covers	running total	next i = i − lowbit(i)
7	−3	7..7	−3	7 − 1 = 6
6	9	5..6	6	6 − 2 = 4
4	10	1..4	16	4 − 4 = 0 → stop

Answer 16, and check the decomposition: 1..4 + 5..6 + 7..7 = 1..7, exactly — three disjoint ranges, no overlap and no gap. That is the invariant, and it is why the query is $O(\log n)$: each step clears one set bit of i, and 7 = 0111 has three.

Update — update(3, +4). Walk up, adding lowbit each time:

i	adds 4 to tree[i]	because tree[i] covers position 3	next i = i + lowbit(i)
3	−1 → 3	3..3 ✓	3 + 1 = 4
4	10 → 14	1..4 ✓	4 + 4 = 8
8	19 → 23	1..8 ✓	8 + 8 = 16 > n → stop

Three nodes touched — exactly the ones whose range contains position 3. prefix_sum(7) now returns 20, up by 4 as it must be.

• Update and query walk in opposite directions, and that is the whole design. i + lowbit(i) enumerates the ranges containing i; i − lowbit(i) enumerates the disjoint ranges tiling the prefix. One trick, used two ways.
• Neither walk touches more than $\log_2 n$ nodes, because each step either clears a set bit (query) or carries one (update).
• tree[5] was never touched by update(3, …) — position 3 is not in 5..5. Updating everything to the right would be $O(n)$; the point of the structure is knowing precisely which $O(\log n)$ nodes care.
• 1-indexing is mandatory. lowbit(0) = 0, so an update at index 0 would loop forever (0 + 0 = 0) and a query at 0 would terminate immediately with 0. That is why tree[0] is unused and every public API here is 1-indexed — the single most common Fenwick bug is passing a 0-indexed position straight through.

Fenwick tree vs. segment tree

Aspect	Fenwick tree (BIT)	Segment tree
Code size	~15 lines, no recursion	~40-60 lines
Supported operations	Invertible ops only (sum, xor)	Any associative op (sum, min, max, gcd, custom)
Range update + range query	Awkward (needs a second BIT)	Native, via lazy propagation
Memory	n + 1 ints	~2n (iterative) to ~4n (recursive)
Conceptual overhead	One bitwise trick	Tree recursion + merge/identity abstraction

When the operation is a plain sum (or xor) and only one of “range update” / “range query” is ever a range (the other being a point), the Fenwick tree wins on simplicity every time.

A quick look at 2D

The same lowbit trick nests cleanly into two dimensions: update and query both become a double loop, one lowbit walk per axis.

fenwick_tree_2d.py

class FenwickTree2D:
    """2D BIT: point update + prefix-rectangle-sum query, O(log rows * log cols) each."""
 
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]
 
    def update(self, r, c, delta):
        i = r
        while i <= self.rows:
            j = c
            while j <= self.cols:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)
 
    def prefix_sum(self, r, c):
        """Sum of the rectangle from (1, 1) to (r, c), inclusive, 1-indexed."""
        total = 0
        i = r
        while i > 0:
            j = c
            while j > 0:
                total += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return total
 
 
grid = FenwickTree2D(4, 4)
grid.update(2, 3, 5)   # point (2,3) += 5
grid.update(4, 4, 7)   # point (4,4) += 7
 
print("prefix sum up to (3, 3):", grid.prefix_sum(3, 3))   # only (2,3) is inside -> 5
print("prefix sum up to (4, 4):", grid.prefix_sum(4, 4))   # both points inside -> 12

The same “subtract off what shouldn’t be counted” idea from 1D range sums extends to rectangles too (inclusion-exclusion over four prefix queries), which is exactly the shape of Range Sum Query 2D - Mutable.

Complexity

Operation	Time
Build (via n point updates)	$O(n \log n)$
Point update	$O(\log n)$
Prefix-sum query	$O(\log n)$
Range-sum query (two prefix queries)	$O(\log n)$
2D point update / prefix query	$O(\log(\text{rows}) \cdot \log(\text{cols}))$

The variant map

Problem / need	What changes	Canonical problem
Prefix / range sum with point updates	the base template	LC 307 Range Sum Query — Mutable
Count smaller elements to the right	index the tree by value, not position; sweep the array right-to-left and query the prefix of the value range	LC 315
Count inversions / reverse pairs	same value-indexed sweep, counting how many already-seen values exceed the current one	LC 493
Values are huge or negative	coordinate-compress first: sort the distinct values, map each to its rank, index the tree by rank	LC 315, LC 493
Range update, point query	store a difference array in the Fenwick tree: add(l, +v), add(r+1, -v), and a point query becomes a prefix sum	—
Range update, range query	two Fenwick trees (one for the linear term, one for the constant) — the standard “BIT with range updates” construction	—
2D prefix sums with updates	a Fenwick tree of Fenwick trees; both walks nest, giving $O(\log m \log n)$	LC 308 (Premium)
XOR instead of sum	replace += with ^=; XOR is its own inverse, so prefix(r) ^ prefix(l-1) works	—
k-th smallest / order statistic	descend the tree bit by bit from the highest power of two, giving $O(\log n)$ instead of $O(\log^2 n)$ binary search over prefix sums	—
Min / max over a range	not a Fenwick tree — min is not invertible, so no prefix subtraction exists. Segment tree, or a sparse table if the array is static	—

Interview follow-ups

They ask	What they’re checking	The answer
“What does tree[i] actually hold?”	Whether you understand the structure or memorised the loops	The sum of the lowbit(i) elements ending at i, i.e. the range (i − lowbit(i), i]. tree[8] covers the whole 8-element array; tree[7] covers only position 7
“Why does update walk up and query walk down?”	The core insight	i + lowbit(i) enumerates the ranges containing i — those are the nodes an update must fix. i − lowbit(i) enumerates the disjoint ranges that tile the prefix — those are the nodes a query must read. One trick, two directions
“Why is it $O(\log n)$?”	Precision	Each step of the query clears one set bit of i; each step of the update carries one. Neither can happen more than $\log_2 n$ times
“Fenwick or segment tree?”	Judgement	Fenwick if the operation is invertible (sum, XOR, count) and updates are point updates — it is ~10 lines, uses one array of size n+1, and has excellent constants. Segment tree the moment you need min/max/gcd, range assignment, or lazy propagation
“Why 1-indexed?”	The trap	Because lowbit(0) = 0: an update at 0 loops forever and a query at 0 returns immediately. tree[0] is deliberately unused
“Now count smaller elements to the right (LC 315)”	Whether you can invert the mental model	Index the tree by value instead of position. Sweep right-to-left; at each element, prefix_sum(value − 1) is how many smaller values have already been seen, then insert the current value. Coordinate-compress first if values are large
“Build in $O(n)$ rather than $O(n \log n)$”	Depth	Copy the values into tree[1..n], then for each i in increasing order push tree[i] into its parent i + lowbit(i) if that is in range. One pass, no logs
“Can it do range minimum?”	Knowing the boundary	Not usefully. Range sum works because prefix(r) − prefix(l−1) inverts the combination, and min has no inverse. A Fenwick tree can do prefix-min with only-decreasing updates, which is a real but narrow special case

Practice — real LeetCode problems

The first is the Fenwick tree with nothing added. The other two are the trick that makes it a competitive-programming staple: index by rank, store counts, and a prefix sum becomes “how many values below this one have I seen”.

LC 307 — Range Sum Query - Mutable · Medium

Problem. Implement NumArray(nums) with update(index, val) setting an element and sumRange(left, right) returning the inclusive sum.

Constraints. 1 <= len(nums) <= 3 * 10**4, -100 <= nums[i], val <= 100, up to 3 * 10**4 calls.

Examples. NumArray([1,3,5]): sumRange(0,2) gives 9, then update(1,2), then sumRange(0,2) gives 8

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The problem exists to make you choose a structure. A plain array gives $O(1)$ update and $O(n)$ query; a prefix-sum array gives $O(1)$ query and $O(n)$ update. With both operations called $3 \times 10^4$ times, either is $10^9$ operations. A Fenwick tree makes both $O(\log n)$.

Time $O(n \log n)$ to build, $O(\log n)$ per operation. Space $O(n)$.

• update sets, it does not add. Storing the current values and applying val - self.nums[index] is the whole adaptation. Adding val directly is the most common wrong answer and it corrupts everything after the first update.
• One-indexing is not decoration. i & -i is 0 when i is 0, so index 0 would loop forever. Converting with i += 1 on the way in is why the public interface can stay zero-indexed.
• i & -i is the lowest set bit, so it is the size of the range that node covers. += walks to the next node that includes i; -= walks to the predecessor block. Being able to say what a node covers is what separates understanding from copying.
• _prefix(left), not _prefix(left + 1), for an inclusive range. Off by one here is silent — it just gives wrong sums.
• Building by n updates is $O(n \log n)$. The $O(n)$ build exists: fill the tree with the raw values, then for each i push tree[i] into tree[i + (i & -i)]. Worth mentioning.

Follow-ups you should expect: “Range update, point query?” — store deltas instead of values: add at left, subtract at right + 1, and a point query is a prefix sum. “Range update, range query?” — two Fenwick trees, or a segment tree with lazy propagation. “Range minimum instead of sum?” — a Fenwick tree cannot do it cleanly, because min has no inverse and prefix subtraction is meaningless; use a segment tree. That contrast is the most-asked question about Fenwick trees. “2D?” — nested trees, $O(\log^2 n)$ per operation.

LC 315 — Count of Smaller Numbers After Self · Hard

Problem. Return an array counts where counts[i] is the number of elements to the right of nums[i] that are smaller than it.

Constraints. 1 <= len(nums) <= 10**5, -10**4 <= nums[i] <= 10**4.

Examples. [5,2,6,1] gives [2,1,1,0] · [-1] gives [0] · [-1,-1] gives [0,0]

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The reframing is the lesson: a Fenwick tree does not have to store the array. Here the index is a value’s rank and the cell is a count, so prefix(r - 1) answers “how many of the values I have inserted so far are smaller than this one”. Sweeping right to left means “inserted so far” is exactly “to the right of me”.

Time $O(n \log n)$. Space $O(n)$.

• Coordinate compression is mandatory. Values are negative and the range is 20,001 wide — workable here by shifting, but the habit generalises to values up to $10^9$ where an array indexed by value is impossible.
• prefix(r - 1), not prefix(r). Strictly smaller excludes equal values, which is why [-1,-1] must give [0,0] and not [1,0].
• Right to left. Sweeping the other way answers a different question (smaller numbers before self), and you would have to reverse and re-derive.
• Query before insert. Inserting first would count the element against itself.
• A single element gives [0] — nothing is to its right.

Three other solutions worth naming, because interviewers often want an alternative: merge sort counting inversions during the merge, a balanced BST / order statistic tree, and in Python a SortedList with bisect_left, which is $O(n \sqrt{n})$ but three lines long and usually fast enough. Say the Fenwick version is what you would write and the SortedList is what you would reach for under time pressure.

Follow-ups you should expect: “Count greater to the right?” — query the suffix instead, or negate the values. “Count smaller to the left?” — sweep the other way. “Count of Range Sum (LC 327)?” — the same technique over prefix sums instead of raw values. “Reverse Pairs (LC 493)?” — also this, with a doubled comparison. “Streaming input?” — Fenwick handles it directly, since inserts are incremental.

LC 1649 — Create Sorted Array through Instructions · Hard

Problem. Insert the elements of instructions one at a time into a new container, keeping it sorted. The cost of each insertion is the minimum of the number of elements already present that are strictly less than it and the number strictly greater. Return the total cost modulo 10**9 + 7.

Constraints. 1 <= len(instructions) <= 10**5, 1 <= instructions[i] <= 10**5.

Examples. [1,5,6,2] gives 1 · [1,2,3,6,5,4] gives 3 · [1,3,3,3,2,4,2,1,2] gives 4

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The same count-by-rank Fenwick tree as the previous problem, sweeping left to right because “already inserted” now means “earlier in the instruction list”.

The arithmetic that carries the whole problem: after k insertions, prefix(v) counts everything <= v, so

$\text{greater} = k - \text{prefix}(v), \qquad \text{smaller} = \text{prefix}(v-1)$

and the duplicates — the values exactly equal to v — are excluded from both, as the definition of cost requires.

Time $O(n \log M)$ where $M$ is the maximum value. Space $O(M)$.

• Duplicates are the whole difficulty. [1,3,3,3,2,4,2,1,2] gives 4, and it is the only test here that distinguishes a correct duplicate rule from k - prefix(v - 1), which would count equal elements as greater.
• No coordinate compression needed, since values are 1..10**5. Compressing anyway is harmless and would be required if the bound were $10^9$.
• k is the count already inserted, which enumerate gives for free — at iteration k exactly k items are in the container.
• Modulus at the end, not inside. min(smaller, larger) must be compared on true values; reducing mid-loop cannot change these magnitudes in Python, but taking the modulus before a comparison is a real bug pattern in languages that overflow, and worth flagging.
• A single instruction costs 0 — nothing is present to compare against.

Follow-ups you should expect: “Values up to $10^9$?” — compress first. “Cost = number of inversions created instead?” — that is LC 315’s count, without the min. “Report the running cost after each insertion?” — accumulate and emit; no change to the structure. “Use a SortedList?” — bisect_left and bisect_right give both counts in $O(\log n)$ with $O(n)$ insertion, which passes here and is far shorter. “Why is min there at all?” — it models inserting from whichever end is closer, which is what makes the problem interesting rather than just an inversion count.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

4 problems

0 easy2 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○307Range Sum Query - MutablemediumThe same problem as the segment tree lesson, solvable here in far fewer lines
• ○673Number of Longest Increasing SubsequencemediumA Fenwick-tree variant (indexed by value, storing "best length" / "count of ways" pairs) that answers each element's transition in $O(\log n)$ instead of the classic $O(n^2)$ DP
• ○315Count of Smaller Numbers After SelfhardA Fenwick tree over coordinate-compressed values, counting smaller elements seen so far while scanning right to left
• ○1649Create Sorted Array through InstructionshardInsert one element at a time, using a Fenwick tree over compressed values to count "how many smaller" and "how many larger" already-inserted elements in $O(\log n)$

Self-check

pch.quizTag Fenwick tree — self-check

1. What does `tree[i]` store?

   A The element at position i B The sum of the lowbit(i) elements ending at i — the range (i − lowbit(i), i] — so tree[8] covers all of 1..8 while tree[7] covers only position 7 C The sum of positions 1..i D The sum of i's two children
   pch.quizShowAnswer

   B — The sum of the lowbit(i) elements ending at i — the range (i − lowbit(i), i] — so tree[8] covers all of 1..8 while tree[7] covers only position 7 — It is neither one node per element nor a balanced tree. The ranges are chosen precisely so that any prefix is a union of O(log n) of them and any position lies in O(log n) of them.

2. Why does update walk `i += i & -i` while query walks `i -= i & -i`?

   A To balance the tree B Because i + lowbit(i) enumerates the ranges CONTAINING i — the nodes an update must fix — while i − lowbit(i) enumerates the disjoint ranges TILING the prefix, which are the nodes a query must read C Because updates are less frequent than queries D To avoid overflow
   pch.quizShowAnswer

   B — Because i + lowbit(i) enumerates the ranges CONTAINING i — the nodes an update must fix — while i − lowbit(i) enumerates the disjoint ranges TILING the prefix, which are the nodes a query must read — One bit trick used in two directions. prefix_sum(7) reads tree[7] + tree[6] + tree[4] = ranges 7..7, 5..6, 1..4 — disjoint, no gaps.

3. Why must a Fenwick tree be 1-indexed?

   A Convention inherited from competitive programming B Because lowbit(0) = 0: an update at index 0 would loop forever (0 + 0 = 0) and a query at 0 would return immediately C Because tree[0] stores the length D It can be 0-indexed with no changes
   pch.quizShowAnswer

   B — Because lowbit(0) = 0: an update at index 0 would loop forever (0 + 0 = 0) and a query at 0 would return immediately — Passing a 0-indexed position straight through is the single most common Fenwick bug. tree[0] is deliberately unused.

4. Can a Fenwick tree answer range MINIMUM queries?

   A Yes, replace += with min() B Not usefully — range sum works because prefix(r) − prefix(l−1) inverts the combination, and min has no inverse. Use a segment tree, or a sparse table for a static array C Yes, with two trees D Yes, but only for positive values
   pch.quizShowAnswer

   B — Not usefully — range sum works because prefix(r) − prefix(l−1) inverts the combination, and min has no inverse. Use a segment tree, or a sparse table for a static array — Invertibility is the precondition. (Prefix-min with only-decreasing updates is a real but narrow special case, worth mentioning as a caveat rather than a solution.)

5. LC 315 asks how many elements to the right of each position are smaller. How is that a Fenwick problem?

   A Build the tree over positions and query suffixes B Index the tree by VALUE rather than position: sweep right-to-left, and prefix_sum(value − 1) counts the smaller values already seen; coordinate-compress first if values are large or negative C Sort the array and use two pointers D It is not; that needs a segment tree
   pch.quizShowAnswer

   B — Index the tree by VALUE rather than position: sweep right-to-left, and prefix_sum(value − 1) counts the smaller values already seen; coordinate-compress first if values are large or negative — Inverting the axis — value-indexed instead of position-indexed — is what turns the whole inversion-counting family (LC 315, LC 493) into this structure.

6. The array is static and you need many range sums. Fenwick tree?

   A Yes, it is always the right tool for range sums B No — a plain prefix-sum array answers each query in O(1) after an O(n) build. A Fenwick tree only earns its log factor when the array is mutated between queries C Yes, because it uses less memory D Only if n > 10^6
   pch.quizShowAnswer

   B — No — a plain prefix-sum array answers each query in O(1) after an O(n) build. A Fenwick tree only earns its log factor when the array is mutated between queries — Reaching for the fancier structure when the simple one strictly dominates is a real interview tell. The Fenwick tree buys you updates, and nothing else.

Recall card

• Cue — prefix or range sums on an array that changes between queries; or inversion-counting (“how many smaller to the right”).
• tree[i] = sum of the lowbit(i) elements ending at i, i.e. the range (i − lowbit(i), i]. That one sentence generates the whole structure.
• lowbit(i) = i & -i — isolates the lowest set bit.
• Update — while i <= n: tree[i] += delta; i += i & -i (walk up, the ranges containing i).
• Query — while i > 0: total += tree[i]; i -= i & -i (walk down, the disjoint ranges tiling the prefix).
• Range sum — prefix(r) - prefix(l-1). Requires an invertible operation: sum, XOR, count.
• 1-indexed, always — lowbit(0) = 0 loops forever.
• Cost — $O(\log n)$ update and query, $O(n)$ space, $O(n \log n)$ naive build or $O(n)$ with the push-to-parent build.
• Inversion problems — index by value, sweep the array, coordinate-compress first.
• Not for min/max/gcd — no inverse, so use a segment tree or, if static, a sparse table.

Recap

• i & (-i) isolates the lowest set bit of i — the size of the range index i is responsible for.
• Update walks up (i += lowbit(i)); prefix query walks toward zero (i -= lowbit(i)); both are $O(\log n)$.
• Range sum is just two prefix queries subtracted, which only works because addition is invertible — min/max can’t do this, which is the Fenwick tree’s one real limitation next to a segment tree.
• A 2D Fenwick tree nests the same trick along both axes for rectangle sums, at $O(\log(\text{rows}) \cdot \log(\text{cols}))$ per operation.

Between this lesson and the previous one, the segment tree and the Fenwick tree cover almost every “range query + update” problem competitive programming throws at you — reach for the Fenwick tree first when the operation is a plain sum, and the segment tree when it isn’t (or when range updates and range queries both need to be ranges).

Next: Sparse Tables and Range Minimum Query — when the array is static (no updates at all), an even faster $O(1)$-per-query structure becomes possible.