Binary Indexed Tree Coding Problems: 8 Questions with Solutions

How binary indexed tree works, step by step

1. A Fenwick tree keeps, at each index i, the sum of the last i & -i values of a up to i, where i & -i is the value of i's lowest set bit. So 6 = 0110 covers two values, 4 = 0100 covers four, and each odd index covers just itself.
2. The odd indices 1, 3, 5 and 7 have lowest bit 1, so each of their blocks holds a single value: t[i] = a[i].
3. 2 = 0010 and 6 = 0110 have lowest bit 2, so their blocks hold two values: t[2] = a[1] + a[2] = 5 and t[6] = a[5] + a[6] = 9.
4. t[4] covers a[1..4] = 10, and t[8] covers all 8 values, 19. The blocks nest like the marks on a ruler, so any prefix of a is a few of them laid end to end.
5. Update a[3] += 2. Every block containing index 3 must change; the first is t[3] itself, now 1. Adding the lowest bit, 3 + 1 = 4, jumps to the next block that contains it.
6. i = 4: t[4] covers a[1..4], which includes index 3, so it becomes 12. Next, 4 + 4 = 8.
7. i = 8: t[8] covers a[1..8] and becomes 21. 8 + 8 = 16 is past the end, so the update stops after 3 blocks, one per bit: O(log n).
8. Now the prefix sum a[1..7]. Start at i = 7: t[7] covers a[7..7], so take -3. Removing the lowest bit, 7 - 1 = 6, moves to the block that ends just before it.
9. i = 6: t[6] covers a[5..6], so take 9 (running total 6). Then 6 - 2 = 4.
10. i = 4: take t[4] = 12, and 4 - 4 = 0 ends the walk: sum(1..7) = -3 + 9 + 12 = 18, from 3 blocks. Both walks take O(log n) steps, one per set bit, against O(n) for a plain array.

Binary Indexed Tree study plan

7 of the 8 Binary Indexed Tree problems (4 medium and 3 hard) over 6 days, about 5 h 5 min in all — the pattern first, then easiest to hardest. After that, the other 1 in the full list below are practice at your own pace.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

• Count Inversions Medium

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Queries on a Permutation With Key Medium
• Number of Longest Increasing Subsequence Medium

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Queue Reconstruction by Height Medium

Day 4

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

• Count of Smaller Numbers After Self Hard

Day 5

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Count of Range Sum Hard

Day 6

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Reverse Pairs Hard

Binary Indexed Tree: the essentials

When to reach for it

Counting pairs i < j by value — inversions, smaller elements after each one, reverse pairs, range sums within bounds — when n reaches 10⁵ and the pair loop is O(n²). Also running totals under single-element changes, or an item's position in a list being rearranged. It needs an inverse, as sums and XOR have; for range minimums use a Segment Tree.

The pattern

Positions start at 1. Cell i holds the sum of the last i & -i values up to position i, so add climbs by adding the lowest set bit and prefix descends by clearing it. For inversions, compress the values to ranks 1 to m and scan: the earlier values greater than x number seen - prefix(tree, rank[x]); then call add(tree, rank[x], 1).

def add(tree, i, delta):                # tree[0] is unused; i starts at 1
    while i < len(tree):
        tree[i] += delta
        i += i & -i                     # climb: add the lowest set bit

def prefix(tree, i):                    # sum of positions 1..i
    total = 0
    while i > 0:
        total += tree[i]
        i -= i & -i                     # descend: clear the lowest set bit
    return total

Cost

O(log n) per add and per prefix, with n + 1 cells of memory. Counting pairs over n elements is O(n log n), including the sort that compresses the values. Any range sum is prefix(r) - prefix(l - 1).

Common mistakes

• Using position 0: 0 & -0 is 0, so add loops for ever. Shift every position up by one.
• Skipping coordinate compression when values are negative or reach 10⁹.
• prefix(rank) where prefix(rank - 1) was meant; that choice decides whether equal values count.
• Reading tree[i] as the value at i; that is prefix(i) - prefix(i - 1).

Start with

• Count Inversions: ranks and prefix counts in one scan.
• Queries on a Permutation With Key: positions that shift as items move to the front.
• Count of Smaller Numbers After Self: the same count, scanning from the right.

All binary indexed tree problems

Medium (4)

• Queries on a Permutation With Key Array, Simulation
• Count Inversions Array, Divide and Conquer, Fenwick Tree
• Queue Reconstruction by Height Array, Greedy, Sorting
• Number of Longest Increasing Subsequence Array, Dynamic Programming

Hard (4)

• Create Sorted Array Through Instructions Array, Binary Search, Divide and Conquer
• Reverse Pairs Array, Binary Search, Divide and Conquer
• Count of Range Sum Fenwick Tree, Divide and Conquer, Prefix Sum
• Count of Smaller Numbers After Self Array, Fenwick Tree, Divide and Conquer

Companies that ask binary indexed tree problems

• Amazon 8 problems on binary indexed tree
• Google 7 problems on binary indexed tree
• Meta 3 problems on binary indexed tree
• Microsoft 3 problems on binary indexed tree
• Flipkart 1 problem on binary indexed tree
• Oracle 1 problem on binary indexed tree
• Uber 1 problem on binary indexed tree

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems