Binary Indexed Tree (Fenwick Tree)

Core Concepts

Binary Indexed Tree (BIT / Fenwick Tree) — a 1-indexed array tree of size n+1 that stores partial sums so that any prefix sum sum(1..i) and any point update can each be answered in O(log n) time and O(n) space. The structure exploits the binary representation of indices to determine which positions each cell is responsible for.

Responsibility range — cell tree[i] stores the sum of arr[i - lowbit(i) + 1 .. i], where lowbit(i) = i & (-i) is the value of i's lowest set bit. The number of elements covered equals lowbit(i).

lowbit operation — lowbit(i) = i & (-i) isolates the least significant set bit of i. It drives both the query (move to parent by subtracting lowbit) and the update (move to next responsible ancestor by adding lowbit).

Prefix query — sum(1..i) is computed by summing tree[i], tree[i - lowbit(i)], tree[i - lowbit(i) - lowbit(...)], etc., until the index reaches 0. At most O(log n) cells are visited.

Point update — adding delta to position i requires updating tree[i], tree[i + lowbit(i)], and so on, until the index exceeds n. At most O(log n) cells are updated.

Range sum query — sum(l..r) = prefix(r) - prefix(l-1). All range sum queries reduce to two prefix queries.

1-indexed convention — BIT indices start at 1. Index 0 is a sentinel; tree[0] is never read or written. Input arrays must be remapped to 1-indexed before use.

---

Structural Invariants

---

Internal Representation

Flat 1-indexed array — the only standard representation. Allocate tree = [0] * (n + 1). Index 0 is unused. All arithmetic is index arithmetic on integers; no pointers, no nodes.

tree = [0] * (n + 1)   # index 0 unused; valid indices 1..n

Space: O(n). The tree has no explicit parent/child pointers — the parent of index i in the update path is i + lowbit(i); in the query path it is i - lowbit(i). The "tree" structure is implicit in these two traversals.

Build from array — two approaches:

• n updates: call update(i, arr[i-1]) for each i in 1..n. Time: O(n log n).
• O(n) build: fill tree[i] = sum of arr[i - lowbit(i) + 1 .. i] directly, then for each i, propagate to parent p = i + lowbit(i) if p <= n: tree[p] += tree[i]. This is O(n) and preferred for large inputs.

for i in range(1, n + 1):
    tree[i] += arr[i - 1]
    p = i + (i & -i)
    if p <= n: tree[p] += tree[i]

2D BIT — a BIT of BITs. Outer index i, inner index j; each cell tree[i][j] covers a rectangle determined by the responsibility ranges of both indices. Update and query both walk two nested loops, each O(log n), giving O(log² n) per operation.

---

Types / Variants

---

Topic-Specific Operations

Update (Point Add)

Add delta to position i. Walk up the tree: at each step, add delta to tree[i] and move to the next responsible ancestor by setting i += lowbit(i). Stop when i > n. Time: O(log n).

while i <= n:
    tree[i] += delta; i += i & -i

Prefix Query

Return sum(1..i). Walk down: accumulate tree[i] and move to the next partial sum by setting i -= lowbit(i). Stop when i == 0. Time: O(log n).

s = 0
while i > 0:
    s += tree[i]; i -= i & -i
return s

Range Query

sum(l..r) = prefix(r) - prefix(l-1). Two calls to the prefix query. The subtraction is exact because prefix sums are computed independently. Time: O(log n).

Point Query (single element)

arr[i] = prefix(i) - prefix(i-1). Equivalent to a range query of length 1. Alternatively, maintain the original array separately if point reads are frequent; the BIT itself does not store individual element values.

Range Update (Difference BIT)

To add v to all positions in [l, r], treat the BIT as storing a difference array: update(l, +v) and update(r+1, -v). A point query at position i returns prefix(i) of the difference BIT, which equals the total delta applied to position i. Time: O(log n) per range update, O(log n) per point query.

Find k-th Element (Walk Down)

Given a BIT storing frequencies, find the smallest index whose prefix sum reaches k. Walk bit-by-bit from the highest power of 2 down to 1, greedily deciding whether to go right (subtract the left subtree's sum from k and advance the index). Time: O(log n) without calling prefix query repeatedly.

pos = 0
for pw in reversed([1 << i for i in range(log2_n)]):
    if pos + pw <= n and tree[pos + pw] < k:
        pos += pw; k -= tree[pos]
return pos + 1

---

Key Algorithms

Inversion Count

Count pairs (i, j) with i < j and arr[i] > arr[j]. Coordinate-compress values to 1..n. Process elements left to right: for each element v, the number of already-inserted elements greater than v is prefix(n) - prefix(v). Insert v (update BIT at v by 1). Total inversions = sum of these counts. Time: O(n log n).

Key insight: inserting elements in left-to-right order converts "elements to the left that are greater" into a suffix-sum query on the frequency BIT, which is a prefix-sum complement.

Longest Increasing Subsequence (BIT optimisation)

Process elements in left-to-right order. For each element v (coordinate-compressed), LIS_ending_at_v = 1 + BIT_max.query(v-1), where the BIT tracks the maximum LIS length seen so far for each value. Update BIT_max at position v with the new LIS length. Time: O(n log n).

Key insight: the BIT-max variant replaces the patience-sorting binary search with a BIT prefix-max query; both give O(n log n) but the BIT generalises to weighted LIS.

Range Sum with Range Updates (Two-BIT Formula)

To support both range-add updates and range-sum queries simultaneously, maintain two BITs B1 and B2. For a range add of v to [l, r]:

• B1.update(l, v), B1.update(r+1, -v)
• B2.update(l, v*(l-1)), B2.update(r+1, -v*r)

Prefix sum sum(1..i) = B1.query(i)*i - B2.query(i). Time: O(log n) per operation.

Key insight: the formula decomposes the range-sum into two prefix-sum contributions that cancel correctly at boundaries, without lazy propagation.

2D BIT for Rectangle Sums

For a 2D grid, nest two BIT update/query loops. Update at (r, c) walks all r' = r + lowbit(r) in the outer loop and all c' = c + lowbit(c) in the inner loop. Rectangle sum (r1,c1)-(r2,c2) uses four prefix queries with inclusion-exclusion. Time: O(log² n) per operation.

Offline Rank / Order-Statistic Queries

For queries "how many elements inserted so far are ≤ v": coordinate-compress all values appearing in updates and queries; build a BIT over the compressed value domain. Each insert increments the frequency at the compressed index; each rank query is a prefix sum. Enables counting inversions, finding k-th smallest in a stream, and offline range order-statistics. Time: O(n log n) with compression.

---

Advanced Techniques

Merge of BIT and Coordinate Compression for 2D Range Counting

Problem class: "Count points (x, y) with x in [x1, x2] and y in [y1, y2]" or "count pairs satisfying two simultaneous ordering constraints."

Mechanism: Sort events by one coordinate (e.g., process x left-to-right). Use a BIT over the y coordinate (after coordinate compression). Each insert is a BIT update at y; each query is a prefix-sum difference prefix(y2) - prefix(y1-1) at the current x sweep position.

When to use over simpler alternatives: Use over 2D BIT when the grid is too large (x up to 10^9) and coordinate compression on y only is feasible. Use over merge sort tree when updates are online. Do not use when both dimensions are large and uncompressible — dynamic segment tree is needed then.

Complexity: O(n log n) time, O(n) space after compression.

Walk-Down (Binary Lifting on BIT) for k-th Element

Problem class: Find the k-th smallest inserted element (or k-th prefix sum position) in O(log n) without O(log² n) binary search over prefix queries.

Mechanism: Instead of binary-searching over prefix(mid) >= k, walk bit-by-bit from the highest power of 2 downward. At each step, check if the current subtree sum is less than k; if so, commit to that subtree and subtract its sum from k. Produces the answer in exactly log n steps, each O(1).

When to use over alternatives: Use over binary search on BIT (which costs O(log² n)) whenever the bottleneck is the k-th query. Do not use when the BIT stores non-frequency data where individual subtree sums do not represent element counts (e.g., weighted sums where "k-th element" is not well-defined).

Complexity: O(log n) per query; same O(log n) update as standard BIT.

BIT as Auxiliary Structure in Offline Query Processing

Problem class: Offline range queries of the form "count elements in a[l..r] satisfying a value predicate" — e.g., count elements less than v, count inversions in a subarray.

Mechanism: Sort queries by right endpoint. Process elements left to right; as each element a[i] is added, update the BIT at its value. When the right endpoint of a query reaches i, answer by querying the BIT. For left-endpoint correction, subtract the BIT state at l-1 (store snapshots or process in two sweeps using persistent BIT / offline subtraction).

When to use over alternatives: Use over persistent segment tree when memory is constrained (BIT uses O(n) per snapshot vs. O(n log n) for persistent tree). Use over merge sort tree when updates are allowed and offline processing is acceptable. Do not use when queries are online (must answer before seeing the next query) — persistent structure is needed.

Complexity: O(n log n) time, O(n) space.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Index 0 in update loop: if i ever reaches 0 in update, the loop i += lowbit(i) never terminates (since lowbit(0) = 0). Always start updates and queries from index ≥ 1; map 0-indexed input arrays to 1-indexed before calling BIT operations.

• Query called with i = 0: prefix(0) should return 0 without entering the loop; this is correct since the while i > 0 guard handles it. However, calling prefix(-1) (from prefix(l-1) when l = 0 in 0-indexed input) is a silent error — ensure l is 1-indexed.

• Off-by-one in coordinate compression: if values are compressed to 0..k-1 instead of 1..k, index 0 enters the BIT causing the infinite-loop bug above. Always compress to 1..k.

• Range update endpoint at r+1 > n: in the difference BIT, update(r+1, -v) for r = n writes to index n+1, which is out of bounds if tree has size n+1. Allocate tree = [0] * (n + 2) when using the difference BIT variant.

• Two-BIT formula sign error: sum(1..i) = B1.query(i)*i - B2.query(i). A common mistake is writing + instead of - for B2, or multiplying by the wrong factor. Derive the formula from first principles on a small example before coding under pressure.

• BIT-max is not invertible: unlike sum, you cannot "undo" a max update. Once tree[i] is set to a large value, decreasing it requires rebuilding. Do not use BIT-max when elements can decrease — use a segment tree instead.

• Coordinate compression including query values: when BIT is used for offline order-statistics, the compression must include all values that appear in both updates and queries. Compressing only update values leaves query values unmapped.

• All-equal values: inversion count is 0 for an array where all elements are equal. BIT over compressed values maps everything to the same index; prefix(n) - prefix(v) evaluates to 0 correctly only if v is the maximum rank. Confirm the compression maps the maximum value to n_distinct not n_distinct - 1.

• Integer overflow in two-BIT formula: B1.query(i) * i can overflow if both values are large. In Python this is safe; in other languages use 64-bit integers explicitly.

---

Implementation Notes

• Python's while i <= n: tree[i] += d; i += i & -i is the complete update; no helper beyond the loop. The symmetry with the query loop (same lowbit operation, opposite direction) is the key to remembering both without a template.
• lowbit(i) = i & (-i) works in Python because Python integers are arbitrary-precision and two's complement negation is well-defined. No special handling needed.
• For the walk-down k-th element, precompute log2_n = n.bit_length() and iterate powers 1 << (log2_n - 1) down to 1. This avoids recomputing the highest bit each call.
• When building a BIT from an array in O(n), the in-place propagation approach (tree[p] += tree[i] for parent p) is faster than n individual update calls (O(n) vs O(n log n)), but both produce identical results.
• 2D BIT indexing: the inner loop variable must be reset to j (the original column) at the start of each outer loop iteration; a common bug is continuing the inner variable across outer iterations.
• sys.stdout.reconfigure(encoding="utf-8") must appear at the top of scripts on Windows; BIT output with large sums may include wide characters.
• For multiple independent test cases, reset with tree[:] = [0] * (n + 1) rather than reallocating; avoids repeated allocation overhead.
• Python BIT is fast enough for n = 2×10^5 with LeetCode's time limits; for n = 10^6, consider PyPy or a Cython-compiled version in competitive settings.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Inversion Count / Count Smaller

• Count of Smaller Numbers After Self (LC 315) — BIT over coordinate-compressed values; process right-to-left
• Global and Local Inversions (LC 775) — inversion count with structural constraint
• Reverse Pairs (LC 493) — modified inversion count with a[i] > 2*a[j]; requires careful compression

Dynamic Prefix Sum

• Range Sum Query — Mutable (LC 307) — baseline BIT: point update + range sum query
• Corporate Flight Bookings (LC 1109) — difference BIT for range updates + point reads

Order Statistics / Rank

• K-th Smallest Element in a Sorted Matrix (LC 378) — BIT-based counting alternative to binary search
• Find the Kth Largest Integer in the Array (LC 1985) — frequency BIT with walk-down
• Number of Longest Increasing Subsequence (LC 673) — BIT-max tracking both length and count

LIS and DP Optimisation

• Longest Increasing Subsequence (LC 300) — BIT-max over compressed values; O(n log n)
• Russian Doll Envelopes (LC 354) — 2D LIS reduced to 1D with sorting + BIT
• Create Sorted Array through Instructions (LC 1649) — insert-and-count pattern; BIT inversion count

2D and Hard

• Count of Range Sum (LC 327) — BIT over prefix sums for range-sum-in-range counting
• Number of Flowers in Full Bloom (LC 2251) — offline sweep + BIT for interval point queries
• Minimum Number of Operations to Make Array Continuous (LC 2009) — sliding window + BIT for counting valid elements

Additional LeetCode Coverage

• Find the Longest Valid Obstacle Course at Each Position (LC 1964)

Clarification Questions to Ask

• "Are updates point updates (change one index) or range updates (change a range)?" — determines whether a standard BIT, difference BIT, or two-BIT formula is needed.
• "Are queries prefix sums, range sums, or point values?" — range sums need two prefix calls; point values need either a separate array or a difference BIT.
• "What is the range of values?" — values up to 10^9 require coordinate compression before building a value-domain BIT.
• "Are queries online (must answer before seeing the next) or offline?" — offline enables right-endpoint sweep; online requires the BIT to be fully dynamic.
• "Can elements be deleted (decremented to zero) as well as inserted?" — subtraction updates are fine for sum BITs; BIT-max does not support deletions.
• "Is 'inversion' defined as strictly greater than or greater than or equal?" — affects whether to query prefix(v-1) or prefix(v) before inserting v.

Common Interview Mistakes

• Starting a BIT at index 0 — causes an infinite loop in the update or a missing cell in the query; always start at index 1 and remap input accordingly.
• Using BIT for range min/max queries — BIT only supports prefix-invertible aggregates (sum, XOR, product); min/max are not invertible (min(a, b) - min(a, x) is not the min of a subrange). Use a segment tree for min/max.
• Forgetting to add tree[n+1] padding for difference BIT — writing update(r+1, -v) when r == n overflows the array; always allocate n+2.
• Not compressing query values in order-statistic BITs — if queries reference values not present in the update set, they map to out-of-range indices or return wrong counts.
• Applying the two-BIT formula with wrong signs or the wrong multiplier (i vs i-1) — the formula is derived; do not memorise it, re-derive from sum(1..i) = sum_j(B1[j] * i - B2[j]).
• Using BIT-max and then trying to "undo" an update — BIT-max is write-once increasing; if the problem requires rollbacks or decreases, it cannot be used without a segment tree.
• Calling prefix(l - 1) when l is 1-indexed and equals 1 — correctly returns prefix(0) = 0; ensure the loop guard while i > 0 handles this without off-by-one.

Typical Follow-Up Escalations

• "Your BIT handles point updates — now support range updates too." → Switch to difference BIT (for range update + point query) or two-BIT formula (for range update + range query).
• "Now find the k-th smallest element efficiently." → Add walk-down traversal; O(log n) vs. O(log² n) for binary search on prefix query.
• "Can your BIT support range minimum queries?" → No — min is not invertible over a prefix; switch to a segment tree with min aggregate.
• "The values go up to 10^9 — how do you handle coordinate compression?" → Collect all values from updates and queries, sort and deduplicate, map to ranks 1..k; then the BIT operates on ranks.
• "Now support both range updates and range sum queries." → Two-BIT formula; walk through the B1 and B2 update and derive the prefix sum formula.
• "Extend to 2D: point updates and rectangle sum queries." → 2D BIT with nested update/query loops; O(log² n) per operation.
• "Your solution is O(n log n) — can you do better?" → O(n) with a static prefix array, but only if there are no updates; with updates, O(n log n) is optimal for comparison-based models.