SyntaxPilot
Courses/DSA and Coding Problems/Lesson 83
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 83 of 90

Fenwick tree: count of smaller numbers after self (hard)

queued

These are the notes for DSA episode 83. A teacher has the marks register in roll-number order and wants, for every student, how many students after them scored less. We try the obvious way, checking everyone after each student (correct, then Time Limit Exceeded on half a million students), then walk the register from the right keeping a tally of the marks already seen. The answer becomes "how many seen marks are smaller", a prefix sum over the tally, and the tally changes at every step: prefix sums with updates, last episode's problem. Instead of a segment tree we build the ten-line Fenwick tree (binary indexed tree), where box i covers the last i & -i positions. Then three real bugs: walking left to right, position 0 (an endless loop), and counting equal marks. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problem, in real life

The marks register In code
Marks in roll-number order the array a
"Students after you" indices j > i
"Scored less than you" a[j] < a[i]
The teacher's tally marks of marks already seen cnt[m] (kept in a Fenwick tree)
Answer for each student res[i]

Every word, from zero

  • Brute force: trying every possibility directly; here, every pair (i, j).
  • Pair (i, j) with i < j: two positions, the first before the second. There are n(n − 1)/2 of them.
  • Tally / frequency array: cnt[m] = how many times the value m has been seen so far.
  • Prefix sum: the total of the first k entries; "how many seen marks are below v" is a prefix sum of the tally.
  • Point update: changing one entry, here cnt[v]++.
  • Binary: writing numbers with digits 0 and 1; 6 = 110, 13 = 1101.
  • Lowest set bit: the rightmost 1 in the binary form; i & -i gives it (6 & -6 = 2, 8 & -8 = 8).
  • Two's complement: how Java stores negative ints; -i is "flip every bit of i, then add 1", which is why i & -i works.
  • Fenwick tree / binary indexed tree (BIT): an array where box i holds the sum of the i & -i positions ending at i; prefix sums and point updates in O(log n).
  • 1-indexed: positions start at 1 (index 0 is unused).
  • Offset (shift): adding a constant so that values −10000..10000 become positions 1..20001.
  • Coordinate compression: replacing values by their rank in sorted order, so huge values fit in a small tree.
  • Inversion: a pair i < j with a[i] > a[j]; the total of today's answers is the number of inversions.
  • Strictly smaller: <, not <=.

Problem statement

Given an integer array a (each value between −10⁴ and 10⁴), return a list res where res[i] is the number of indices j > i with a[j] < a[i] (LeetCode 315, Hard; n ≤ 10⁵ there, we test 5 × 10⁵).

Input Output Why
[5, 2, 6, 1] [2, 1, 1, 0] after 5 come 2 and 1; after 2, only 1; after 6, 1
[62, 48, 75, 48, 90, 30] [3, 1, 2, 1, 1, 0] the marks register
[-1] [0] one element
[2, 2, 1] [1, 1, 0] equal is not smaller
[-10000, 10000, -10000] [0, 1, 0] the extreme values

Obvious idea: check everyone after each student

import java.util.*;

public class Main {
    static List<Integer> countSmaller(int[] a) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            int c = 0;
            for (int j = i + 1; j < a.length; j++)
                if (a[j] < a[i]) c++;
            res.add(c);
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(countSmaller(new int[]{5, 2, 6, 1}));
        System.out.println(countSmaller(new int[]{62, 48, 75, 48, 90, 30}));
        System.out.println(countSmaller(new int[]{-1}));
        System.out.println(countSmaller(new int[]{2, 2, 1}));
        System.out.println(countSmaller(new int[]{-10000, 10000, -10000}));
    }
}

Output (real):

[2, 1, 1, 0]
[3, 1, 2, 1, 1, 0]
[0]
[1, 1, 0]
[0, 1, 0]

The big test

Half a million marks from new Random(7); we print the total of all answers and the time:

        int n = 500_000;
        int[] a = new int[n];
        Random rnd = new Random(7);
        for (int i = 0; i < n; i++) a[i] = rnd.nextInt(20001) - 10000;
        long t0 = System.nanoTime(), total = 0;
        for (int c : countSmaller(a)) total += c;
        System.out.println(total + " pairs, " + (System.nanoTime() - t0) / 1000000 + " ms");

Result with the brute force: Time Limit Exceeded (25 s).

Why is it slow?

There are n(n − 1)/2 pairs: for n = 500,000 about 1.25 × 10¹¹ comparisons, and students near the end are re-read by everyone before them.

The key insight: walk from the right with a tally

Walk from the last student to the first. When you reach student i, the students you have already seen are exactly the students after i. Keep a tally cnt[m] of the marks seen so far:

res[i] = cnt[-10000] + cnt[-9999] + ... + cnt[a[i] - 1]     (marks strictly below a[i])
cnt[a[i]]++

By hand, for 5 2 6 1:

Step Student Seen before this step Smaller seen res
1 1 { } none 0
2 6 {1} 1 1
3 2 {1, 6} 1 1
4 5 {1, 2, 6} 1, 2 2

The two moves are a prefix sum and a point update on the tally: exactly episode 82's problem. Looping over the tally would cost 20,001 steps per student; a segment tree would do both in O(log V). The Fenwick tree does it in about ten lines.

The Fenwick tree

Positions are 1..n. Box i stores the sum of the i & -i positions ending at i:

i binary i & -i box i covers
1 0001 1 1
2 0010 2 1..2
3 0011 1 3
4 0100 4 1..4
5 0101 1 5
6 0110 2 5..6
7 0111 1 7
8 1000 8 1..8
  • prefix(i): add box i, then i -= i & -i (drop the block), until i == 0. prefix(7) = box 7 + box 6 + box 4 (7 → 6 → 4 → 0).
  • add(i): add to box i, then i += i & -i, until past n. add(3) touches boxes 3 → 4 → 8: exactly the boxes whose blocks contain 3.

Each jump removes (or carries) one bit, so both loops take at most log₂ n + 1 steps.

Marks −10000..10000 become positions v = a[i] + 10001, i.e. 1..20001, and the answer is prefix(v − 1) (strictly smaller).

Solution in Java

import java.util.*;

public class Main {
    static int[] bit;
    static void add(int i) {
        for (; i < bit.length; i += i & -i) bit[i]++;
    }
    static int prefix(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
    static List<Integer> countSmaller(int[] a) {
        bit = new int[20002];
        Integer[] res = new Integer[a.length];
        for (int i = a.length - 1; i >= 0; i--) {
            int v = a[i] + 10001;
            res[i] = prefix(v - 1);
            add(v);
        }
        return Arrays.asList(res);
    }
    public static void main(String[] args) {
        System.out.println(countSmaller(new int[]{5, 2, 6, 1}));
        System.out.println(countSmaller(new int[]{62, 48, 75, 48, 90, 30}));
        System.out.println(countSmaller(new int[]{-1}));
        System.out.println(countSmaller(new int[]{2, 2, 1}));
        System.out.println(countSmaller(new int[]{-10000, 10000, -10000}));
    }
}

Output (real):

[2, 1, 1, 0]
[3, 1, 2, 1, 1, 0]
[0]
[1, 1, 0]
[0, 1, 0]

On the big test: 62502274660 pairs, 36 ms.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

vector<int> bit;
void add(int i) { for (; i < (int)bit.size(); i += i & -i) bit[i]++; }
int prefix(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }

vector<int> countSmaller(const vector<int>& a) {
    bit.assign(20002, 0);
    vector<int> res(a.size());
    for (int i = (int)a.size() - 1; i >= 0; i--) {
        int v = a[i] + 10001;
        res[i] = prefix(v - 1);
        add(v);
    }
    return res;
}

void show(const vector<int>& r) {
    cout << "[";
    for (size_t i = 0; i < r.size(); i++) cout << (i ? ", " : "") << r[i];
    cout << "]\n";
}

int main() {
    show(countSmaller({5, 2, 6, 1}));
    show(countSmaller({62, 48, 75, 48, 90, 30}));
    show(countSmaller({-1}));
    show(countSmaller({2, 2, 1}));
    show(countSmaller({-10000, 10000, -10000}));
}

Output (real):

[2, 1, 1, 0]
[3, 1, 2, 1, 1, 0]
[0]
[1, 1, 0]
[0, 1, 0]

The same solution in Python

def count_smaller(a):
    bit = [0] * 20002

    def add(i):
        while i < len(bit):
            bit[i] += 1
            i += i & -i

    def prefix(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    res = [0] * len(a)
    for i in range(len(a) - 1, -1, -1):
        v = a[i] + 10001
        res[i] = prefix(v - 1)
        add(v)
    return res


print(count_smaller([5, 2, 6, 1]))
print(count_smaller([62, 48, 75, 48, 90, 30]))
print(count_smaller([-1]))
print(count_smaller([2, 2, 1]))
print(count_smaller([-10000, 10000, -10000]))

Output (real):

[2, 1, 1, 0]
[3, 1, 2, 1, 1, 0]
[0]
[1, 1, 0]
[0, 1, 0]

Three real bugs

Bug 1: walking left to right

The tally then holds the students before i, so it counts smaller numbers before each element:

[0, 0, 2, 0]

Expected [2, 1, 1, 0].

Bug 2: offset 10000 instead of 10001

-10000 becomes position 0. 0 & -0 is 0, so add jumps by zero forever:

countSmaller(new int[]{-10000, 5})  →  Time Limit Exceeded (the add loop never ends)

That is why a Fenwick tree starts at position 1.

Bug 3: prefix(v) instead of prefix(v − 1)

prefix(v) also counts equal marks:

[2, 1, 0]

Expected [1, 1, 0].

Complexity

Approach Time Extra space n = 500,000
Check everyone after O(n²) O(1) Time Limit Exceeded
Tally with a plain loop O(n × V) O(V) about 10¹⁰ steps: too slow
Segment tree on the tally (episode 82) O(n log V) O(V) fast
Fenwick tree on the tally O(n log V) O(V) 36 ms
Merge sort counting (alternative) O(n log n) O(n) fast

V = the number of possible values (20,001 here). With coordinate compression V ≤ n.

Common mistakes

Mistake What you see (real) Why Fix
Walk left to right [0, 0, 2, 0] instead of [2, 1, 1, 0] counts smaller before walk from the right
a[i] + 10000 Time Limit Exceeded position 0: i & -i is 0 positions start at 1
prefix(v) [2, 1, 0] instead of [1, 1, 0] equal marks counted prefix(v - 1)
A tree sized by the values when values reach 10⁹ OutOfMemoryError: Java heap space an array of billions coordinate compression
int total of all answers a wrong total for big n 6 × 10¹⁰ pairs long
Arrays.binarySearch on a sorted array with duplicates for ranks equal values get different ranks it returns any matching index remove duplicates first

Mini project: class rank report

Read a CSV of roll,marks. For every student print how many later students they beat, how many earlier students beat them (walk left to right with prefix(V) − prefix(v)), and the total number of inversions as a measure of "how unsorted" the register is.

Practice

1. Count of smaller numbers after self for any values (up to ±5 × 10⁹), with coordinate compression.

2. Count inversions of [5, 2, 6, 1].

3. Range Sum Query - Mutable (LeetCode 307) with a Fenwick tree that adds any amount.

4. Reverse Pairs (LeetCode 493): pairs i < j with a[i] > 2 × a[j].

Solutions
import java.util.*;

public class Main {
    // A Fenwick tree over positions 1..n that can add any amount.
    static class Fenwick {
        long[] t;
        Fenwick(int n) { t = new long[n + 1]; }
        void add(int i, long d) { for (; i < t.length; i += i & -i) t[i] += d; }
        long prefix(int i) { long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
    }
    // Coordinate compression: value -> rank 1..m (equal values share a rank).
    static int[] ranks(long[] a) {
        long[] s = a.clone();
        Arrays.sort(s);
        int m = 0;
        for (int i = 0; i < s.length; i++) if (i == 0 || s[i] != s[i - 1]) s[m++] = s[i];
        int[] r = new int[a.length];
        for (int i = 0; i < a.length; i++) r[i] = Arrays.binarySearch(s, 0, m, a[i]) + 1;
        return r;
    }
    // 1. Count of smaller numbers after self for ANY values (compression instead of a shift).
    static List<Integer> countSmaller(long[] a) {
        int[] r = ranks(a);
        Fenwick f = new Fenwick(a.length);
        Integer[] res = new Integer[a.length];
        for (int i = a.length - 1; i >= 0; i--) {
            res[i] = (int) f.prefix(r[i] - 1);
            f.add(r[i], 1);
        }
        return Arrays.asList(res);
    }
    // 2. Inversions: pairs i < j with a[i] > a[j] = the total of countSmaller.
    static long inversions(long[] a) {
        long total = 0;
        for (int c : countSmaller(a)) total += c;
        return total;
    }
    // 3. Range Sum Query - Mutable with a Fenwick tree.
    static class NumArray {
        Fenwick f; long[] a;
        NumArray(long[] v) { a = v.clone(); f = new Fenwick(v.length); for (int i = 0; i < v.length; i++) f.add(i + 1, v[i]); }
        void update(int i, long v) { f.add(i + 1, v - a[i]); a[i] = v; }
        long sumRange(int l, int r) { return f.prefix(r + 1) - f.prefix(l); }
    }
    // 4. Reverse Pairs (LeetCode 493): i < j and a[i] > 2 * a[j].
    static int reversePairs(int[] nums) {
        int n = nums.length;
        long[] all = new long[2 * n];
        for (int i = 0; i < n; i++) { all[i] = nums[i]; all[n + i] = 2L * nums[i]; }
        long[] s = all.clone(); Arrays.sort(s);
        Fenwick f = new Fenwick(2 * n);
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            int below = lowerBound(s, nums[i]);          // how many sorted values are < nums[i]
            count += (int) f.prefix(below);               // seen 2*a[j] that are < nums[i]
            f.add(lowerBound(s, 2L * nums[i]) + 1, 1);    // add 2*nums[i]
        }
        return count;
    }
    static int lowerBound(long[] s, long x) { int lo = 0, hi = s.length; while (lo < hi) { int m = (lo + hi) / 2; if (s[m] < x) lo = m + 1; else hi = m; } return lo; }
    public static void main(String[] args) {
        System.out.println(countSmaller(new long[]{5_000_000_000L, -7, 5_000_000_000L, 3}));
        System.out.println(inversions(new long[]{5, 2, 6, 1}));
        NumArray na = new NumArray(new long[]{5, 3, 7, 2, 6, 1, 4, 8});
        System.out.print(na.sumRange(2, 6) + " ");
        na.update(3, 10);
        System.out.println(na.sumRange(2, 6));
        System.out.println(reversePairs(new int[]{1, 3, 2, 3, 1}) + " " + reversePairs(new int[]{2, 4, 3, 5, 1}));
    }
}

Output (real):

[2, 0, 1, 0]
4
20 28
2 3

Quick quiz

13 = 1101 in binary. Which boxes does prefix(13) add? A) 13, 12, 8 B) 13, 12, 11 C) 13, 14, 16 D) 1, 2, 4, 8

Answer

A. 1101 → drop the lowest 1 → 1100 (12) → 1000 (8) → 0.

Interview questions

  1. Why walk from the right? So that the tally holds exactly the elements after the current one.
  2. What does i & -i compute, and why? The lowest set bit: in two's complement -i flips every bit above it.
  3. What does Fenwick box i store? The sum of the i & -i positions ending at i.
  4. Why does a Fenwick tree start at 1? At 0, i & -i is 0 and the loops never move.
  5. How do you handle values up to 10⁹? Coordinate compression: sort, remove duplicates, use ranks.
  6. Fenwick vs segment tree? Fenwick: shorter, less memory, prefix-style (invertible) operations. Segment tree: any range, min/max, lazy range updates.
  7. Another O(n log n) solution? Merge sort: while merging, count how many elements from the right half move before each left element.

Glossary

Term Meaning
Tally / frequency array cnt[m] = how many times m was seen
Prefix sum Total of the first k entries
Point update Change one entry
Lowest set bit The rightmost 1 in binary: i & -i
Two's complement How Java stores negative integers
Fenwick tree (BIT) Box i = sum of the i & -i positions ending at i
1-indexed Positions start at 1
Offset A constant added to map values to positions
Coordinate compression Values replaced by their sorted rank
Inversion A pair i < j with a[i] > a[j]
Strictly smaller <, not <=

Summary

  • Checking everyone after each student is O(n²): half a million students time out.
  • Walk from the right with a tally: the answer is a prefix sum of the tally, then one point update.
  • A Fenwick tree does both in O(log V): jump down with i -= i & -i to sum, up with i += i & -i to add.
  • Positions start at 1, the answer is prefix(v − 1), and huge values need coordinate compression.
  • Next episode: sparse table: range minimum query in O(1).