Binary Indexed Tree

What Is a Binary Indexed Tree?

I remember the first time I saw a Binary Indexed Tree — it was during a competitive programming contest, and someone solved a range query problem in minutes while I was still setting up a segment tree. The Fenwick Tree, as it is also known, is one of those rare data structures that makes you smile when you finally understand it. It is elegantly simple, yet its entire mechanism revolves around a single bitwise operation: lowbit(x) = x & -x.

A Binary Indexed Tree (BIT) is a data structure that supports two operations on an array of n elements, both in O(log n) time:

During a coding competition, I used a Fenwick tree to compute running totals of stock prices, and the i & -i trick for isolating the least significant set bit allowed updates in microseconds. That competition problem cemented my appreciation for BITs over segment trees for simple prefix queries.

• Prefix sum query: compute the sum of elements from index 1 to k
• Point update: add a value to element at index k

The genius of the BIT is that it doesn't store the tree explicitly. The tree is implicitly defined by the binary representation of indices. Each index i in the BIT array stores the sum of a range of elements from the original array, where the length of that range is exactly the value of the lowest set bit of i.

The lowbit Operation: x & -x

The lowbit operation is the heart of the Binary Indexed Tree. It returns the value of the lowest set bit in a number. For example, lowbit(12) = 4 because 12 in binary is 1100, and the lowest set bit has value 4 (binary 100).

In two's complement arithmetic, -x is equal to (~x + 1). When you compute x & -x, the addition carries through the trailing zeros and clears bits above the lowest set bit. The result is a power of two representing the lowest set bit of x.

// lowbit in various languages
int lowbit(int x) { return x & -x; }      // C/C++

function lowbit(x) { return x & -x; }     // JavaScript

def lowbit(x): return x & -x              # Python

// Examples:
// lowbit(1)  = 1    (0001 & 1111 = 0001)
// lowbit(6)  = 2    (0110 & 1010 = 0010)
// lowbit(8)  = 8    (1000 & 1000 = 1000)
// lowbit(10) = 2    (1010 & 0110 = 0010)
// lowbit(16) = 16   (10000 & 10000 = 10000)

BIT Implementation

Prefix Sum Query

To compute the prefix sum up to index k, we traverse the tree from k down to 0 by repeatedly subtracting lowbit(k). Each step adds the value stored at that index to our running sum. The index jumps represent moving up the tree — from a child range to its parent range that covers it.

// BIT — Prefix Sum Query
function bitQuery(bit, k) {
    let sum = 0;
    while (k > 0) {
        sum += bit[k];
        k -= lowbit(k);  // move to parent range
    }
    return sum;
}

// Example: query prefix sum up to index 7
// bit[7] covers [7,7], then k=6
// bit[6] covers [5,6], then k=4
// bit[4] covers [1,4], then k=0
// Result: bit[7] + bit[6] + bit[4]
// Total: 3 nodes visited  O(log 7) ≈ O(log n)

Point Update

To update element at index k by delta, we traverse upward by repeatedly adding lowbit(k). Each index we visit contains a range that includes k, so we must update all of them. The traversal goes from k up to n, covering increasingly larger ranges.

// BIT — Point Update
function bitUpdate(bit, n, k, delta) {
    while (k <= n) {
        bit[k] += delta;
        k += lowbit(k);  // move to next range that contains k
    }
}

// Example: update index 3 by +5
// k=3: bit[3] += 5, then k=3+1=4
// k=4: bit[4] += 5, then k=4+4=8
// k=8: bit[8] += 5, then k=8+8=16 (stop if n < 16)
// Total: 3 nodes visited  O(log n)

Complete BIT Class

class FenwickTree {
    constructor(n) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }

    lowbit(x) { return x & -x; }

    // Add delta to element at position k
    add(k, delta) {
        while (k <= this.n) {
            this.tree[k] += delta;
            k += this.lowbit(k);
        }
    }

    // Sum of elements [1, k]
    prefixSum(k) {
        let s = 0;
        while (k > 0) {
            s += this.tree[k];
            k -= this.lowbit(k);
        }
        return s;
    }

    // Sum of elements [l, r]
    rangeSum(l, r) {
        return this.prefixSum(r) - this.prefixSum(l - 1);
    }
}

// Usage example
const bit = new FenwickTree(10);
bit.add(3, 5);          // arr[3] += 5
bit.add(7, 2);          // arr[7] += 2
console.log(bit.rangeSum(1, 5)); // sum of arr[1..5] = 5
console.log(bit.rangeSum(1, 10)); // sum of arr[1..10] = 7

Applications of Binary Indexed Trees

Counting Inversions

One classic application I use frequently is counting inversions in an array — the number of pairs (i, j) where i < j and arr[i] > arr[j]. With a BIT, this runs in O(n log n). Initialize an empty BIT of size max_value. Iterate from left to right: for each element, query how many larger elements have already been seen using prefix sum, then update the BIT at the current element's position.

// Count inversions using BIT
function countInversions(arr) {
    const maxVal = Math.max(...arr);
    const bit = new FenwickTree(maxVal);
    let inversions = 0;

    for (let i = arr.length - 1; i >= 0; i--) {
        // Count elements seen so far that are smaller than arr[i]
        inversions += bit.prefixSum(arr[i] - 1);
        bit.add(arr[i], 1);  // mark current element as seen
    }
    return inversions;
}

// Example: [3, 1, 2]  inversions = 2 (pairs: (3,1), (3,2))

Range Update and Point Query

By using a difference BIT where BIT[i] stores arr[i] - arr[i-1], you can support range updates (add x to every element in [l, r]) and point queries (get value at index k). A range update on the difference BIT becomes two point updates: add(l, x) and add(r+1, -x). A point query at k becomes a prefix sum query on the difference BIT up to k.

Order-Statistic Tree

A BIT can serve as an order-statistic tree — finding the k-th smallest element among the values seen so far. Using a BIT over the value range, each insertion sets a bit at the value's position. To find the k-th smallest, binary search on the prefix sum: find the smallest index where prefixSum(index) >= k. This is O(log n * log maxVal) or O(log maxVal) with BIT binary lifting.

// Find k-th smallest element in values seen so far
function kthSmallest(bit, n, k) {
    // Binary search: find smallest idx where prefixSum(idx) >= k
    let lo = 1, hi = n;
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (bit.prefixSum(mid) >= k) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}