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)withi < j: two positions, the first before the second. There aren(n − 1)/2of them. - Tally / frequency array:
cnt[m]= how many times the valuemhas been seen so far. - Prefix sum: the total of the first
kentries; "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 & -igives it (6 & -6 = 2,8 & -8 = 8). - Two's complement: how Java stores negative
ints;-iis "flip every bit ofi, then add 1", which is whyi & -iworks. - Fenwick tree / binary indexed tree (BIT): an array where box
iholds the sum of thei & -ipositions ending ati; 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..10000become positions1..20001. - Coordinate compression: replacing values by their rank in sorted order, so huge values fit in a small tree.
- Inversion: a pair
i < jwitha[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 boxi, theni -= i & -i(drop the block), untili == 0.prefix(7)= box 7 + box 6 + box 4 (7 → 6 → 4 → 0).add(i): add to boxi, theni += i & -i, until pastn.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
- Why walk from the right? So that the tally holds exactly the elements after the current one.
- What does
i & -icompute, and why? The lowest set bit: in two's complement-iflips every bit above it. - What does Fenwick box
istore? The sum of thei & -ipositions ending ati. - Why does a Fenwick tree start at 1? At 0,
i & -iis 0 and the loops never move. - How do you handle values up to 10⁹? Coordinate compression: sort, remove duplicates, use ranks.
- Fenwick vs segment tree? Fenwick: shorter, less memory, prefix-style (invertible) operations. Segment tree: any range, min/max, lazy range updates.
- 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 & -ito sum, up withi += i & -ito 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).