templates · Bits, range queries & string matching

Fenwick tree (BIT)

  • Range sums while values keep changing (point updates mixed with queries)
  • "How many earlier (or later) values are smaller": count with ranks
  • A plain prefix-sum array would need O(n) work after every update

Fenwick tree (BIT)

the one rule

The invariant

tree[i] holds the sum of the last i & -i elements ending at position i (1-based).

write it from memory

The template

the Fenwick tree

javajava.util.*
/** Point update + prefix sum in O(log n). Positions are 0-based outside, 1-based inside. */class Fenwick {    private final long[] tree;                           // tree[i] = sum of a block ending at i (1-based)     Fenwick(int n) {        tree = new long[n + 1];                          // index 0 is unused    }     /** a[index] += delta */    void add(int index, long delta) {        for (int i = index + 1; i < tree.length; i += i & -i) { // climb: i & -i is the lowest set bit            tree[i] += delta;        }    }     /** a[0] + … + a[index - 1], the sum of the first `count` elements when index = count */    long prefix(int count) {        long sum = 0;        for (int i = count; i > 0; i -= i & -i) {        // walk down, one block at a time            sum += tree[i];        }        return sum;    }     /** a[left] + … + a[right], both inclusive */    long rangeSum(int left, int right) {        return prefix(right + 1) - prefix(left);    }}

Learn the two loops as a pair: add climbs with i += i & -i, prefix walks down with i -= i & -i.

fill in the blanks — only these lines change per problem

  1. line 3What a slot sums: values for range sums, counts for "how many smaller".
  2. line 12How an update merges in: += for sums and counts. (Max works only if values never go down.)
  3. line 27A range is two prefixes subtracted: prefix(right + 1) - prefix(left).

counting with ranks

javajava.util.*
/** Count of Smaller Numbers After Self: for each i, how many later values are smaller. */static List<Integer> countSmaller(int[] nums) {    int[] sorted = Arrays.stream(nums).distinct().sorted().toArray();  // compress values to ranks    Fenwick seen = new Fenwick(sorted.length);           // seen counts per rank, for values to the right    Integer[] out = new Integer[nums.length];    for (int i = nums.length - 1; i >= 0; i--) {         // right to left        int rank = Arrays.binarySearch(sorted, nums[i]);        out[i] = (int) seen.prefix(rank);                // ranks 0..rank-1 = strictly smaller        seen.add(rank, 1);    }    return Arrays.asList(out);}

Values can be huge or negative, so first replace each value by its rank in the sorted list. Then the tree has one slot per rank.

fill in the blanks — only these lines change per problem

  1. line 3Map values to ranks 0..k-1 when they are big, negative or sparse.
  2. line 6Which side you scan from decides the question: right to left asks about later values.
  3. line 8Which prefix to ask for: prefix(rank) for strictly smaller, prefix(rank + 1) for smaller or equal.

complexity

What it costs

time O(log n) per update or query
Each step adds or removes the lowest set bit of i, and an index has at most log₂ n bits.
space O(n)
One long per position, plus an unused cell 0.

watch out

Common bugs

  • Starting the loop at index 0: 0 & -0 is 0, so the loop never moves. Shift to 1-based first.
  • Calling add(i, newValue) for an update instead of add(i, newValue - oldValue).
  • Using int sums; many large values overflow. Keep the tree in long.

use it

Practise it on

learn it properly