Data Structures & AlgorithmsFenwick Trees (Binary Indexed Trees)

Fenwick Trees — Binary Indexed Trees

LevelAdvanced

Duration90 mins

TopicFenwick Trees (Binary Indexed Trees)

3 / 5

Prefix Sum Queries

Querying Cumulative Sums Efficiently

With the structure of Fenwick Trees understood, we now focus on the query operation — the core functionality that makes this data structure valuable. The query operation computes prefix sums: given an index i, return the sum of all elements from index 1 to i.

This seemingly simple operation is the foundation for a wide range of applications. From this single primitive, we can derive:

Range sum queries: Sum of elements in any arbitrary range [l, r]
Frequency queries: Count of elements with certain properties
Running totals: Cumulative statistics up to any point
Order statistics: Finding ranks and quantiles

This page examines the query operation in exhaustive detail — the algorithm, its correctness, variations, optimizations, and practical applications.

What You Will Learn

By the end of this page, you will: • Master the prefix sum query algorithm with complete understanding • Derive range queries from prefix queries • Handle edge cases correctly in production code • Understand query complexity at a deep level • Implement multiple query variations for different use cases • Apply prefix queries to solve real-world problems

The Query Algorithm — Step by Step

Let's formalize the query algorithm and trace through its execution in complete detail.

The Query Goal:

Given an index i (1-indexed), compute:

prefix(i) = A[1] + A[2] + ... + A[i]

The Algorithm:

function query(i):
    sum = 0
    while i > 0:
        sum = sum + BIT[i]
        i = i - (i & -i)    // Remove lowest set bit
    return sum

Why it works:

Recall that BIT[i] stores the sum of elements in the range [i - LSB(i) + 1, i]. The query algorithm collects these non-overlapping ranges by repeatedly stripping the lowest set bit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class FenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    /**
     * Query prefix sum from index 1 to i (inclusive).
     * 
     * @param i - The ending index (1-indexed)
     * @returns The sum A[1] + A[2] + ... + A[i]
     * 
     * Preconditions:
     *   - 1 <= i <= n
     *   - BIT invariant is maintained
     * 
     * Postconditions:
     *   - Returns the exact prefix sum
     *   - BIT is not modified
     */
    query(i: number): number {
        // Validate input
        if (i < 0) return 0;
        if (i > this.n) i = this.n;
        
        let sum = 0;
        
        while (i > 0) {
            sum += this.tree[i];
            i -= i & (-i);  // Remove lowest set bit
        }
        
        return sum;
    }
 
    /**
     * Query with detailed tracing for educational purposes.
     * Returns both the sum and the trace of indices visited.
     */
    queryWithTrace(i: number): { sum: number; trace: number[] } {
        const trace: number[] = [];
        let sum = 0;
        
        while (i > 0) {
            trace.push(i);
            sum += this.tree[i];
            i -= i & (-i);
        }
        
        return { sum, trace };
    }
}
 
// Example usage with trace
const bit = new FenwickTree(16);
// Assume BIT is populated...
 
// Query for i = 13 (binary: 1101)
const result = bit.queryWithTrace(13);
console.log("Indices visited:", result.trace);
// Output: [13, 12, 8]
// 13 (1101) -> 12 (1100) -> 8 (1000) -> 0 (stop)
 
// Query for i = 15 (binary: 1111)
const result2 = bit.queryWithTrace(15);
console.log("Indices visited:", result2.trace);
// Output: [15, 14, 12, 8]
// Visits 4 indices because 15 has 4 set bits

Iteration Count = popcount(i)

The number of iterations in the query loop equals exactly the number of 1-bits (popcount) in i. For i = 13 = 1101₂, we have 3 set bits, so 3 iterations. This is always at most ⌊log₂(n)⌋ + 1 iterations.

Complete Trace Examples

Let's trace the query algorithm for several inputs to build deep intuition:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Query prefix(7):
 
i = 7 (binary: 0111)
├── LSB(7) = 1
├── BIT[7] covers range [7, 7]
├── Add BIT[7] to sum
└── Next: i = 7 - 1 = 6
 
i = 6 (binary: 0110)
├── LSB(6) = 2
├── BIT[6] covers range [5, 6]
├── Add BIT[6] to sum
└── Next: i = 6 - 2 = 4
 
i = 4 (binary: 0100)
├── LSB(4) = 4
├── BIT[4] covers range [1, 4]
├── Add BIT[4] to sum
└── Next: i = 4 - 4 = 0
 
i = 0: STOP
 
Result: BIT[7] + BIT[6] + BIT[4]
      = A[7] + (A[5]+A[6]) + (A[1]+A[2]+A[3]+A[4])
      = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] ✓
 
Iterations: 3 (popcount of 7 = 3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Query prefix(16):
 
i = 16 (binary: 10000)
├── LSB(16) = 16
├── BIT[16] covers range [1, 16]
├── Add BIT[16] to sum
└── Next: i = 16 - 16 = 0
 
i = 0: STOP
 
Result: BIT[16]
      = A[1] + A[2] + ... + A[16] ✓
 
Iterations: 1 (popcount of 16 = 1)
 
This is the best case! Powers of 2 require only ONE access.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Query prefix(11):
 
i = 11 (binary: 1011)
├── LSB(11) = 1
├── BIT[11] covers range [11, 11]
├── Add BIT[11] to sum
└── Next: i = 11 - 1 = 10
 
i = 10 (binary: 1010)
├── LSB(10) = 2
├── BIT[10] covers range [9, 10]
├── Add BIT[10] to sum
└── Next: i = 10 - 2 = 8
 
i = 8 (binary: 1000)
├── LSB(8) = 8
├── BIT[8] covers range [1, 8]
├── Add BIT[8] to sum
└── Next: i = 8 - 8 = 0
 
i = 0: STOP
 
Result: BIT[11] + BIT[10] + BIT[8]
      = A[11] + (A[9]+A[10]) + (A[1]+...+A[8])
      = A[1] + A[2] + ... + A[11] ✓
 
Iterations: 3

Query Iterations by Index
Index i	Binary	popcount	Indices Visited	Ranges Collected
1	0001	1	[1]	[1..1]
4	0100	1	[4]	[1..4]
7	0111	3	[7, 6, 4]	[7..7], [5..6], [1..4]
8	1000	1	[8]	[1..8]
10	1010	2	[10, 8]	[9..10], [1..8]
15	1111	4	[15, 14, 12, 8]	[15], [13..14], [9..12], [1..8]
16	10000	1	[16]	[1..16]

Range Queries from Prefix Queries

While BITs natively support prefix queries, we often need range queries: the sum of elements in an arbitrary range [l, r].

The Key Insight:

For any invertible operation (where we can "subtract" to undo), range queries reduce to prefix queries:

sum(l, r) = prefix(r) - prefix(l - 1)

Visual Explanation:

Array:    [A₁] [A₂] [A₃] [A₄] [A₅] [A₆] [A₇] [A₈]

prefix(r) = A₁ + A₂ + ... + Aₗ₋₁ + Aₗ + ... + Aᵣ
prefix(l-1) = A₁ + A₂ + ... + Aₗ₋₁

Subtraction cancels the common prefix:
sum(l, r) = Aₗ + ... + Aᵣ ✓

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class FenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    // Prefix sum query
    private prefixSum(i: number): number {
        if (i <= 0) return 0;
        if (i > this.n) i = this.n;
        
        let sum = 0;
        while (i > 0) {
            sum += this.tree[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    /**
     * Query the sum of elements in range [l, r] (1-indexed, inclusive).
     * 
     * @param l - Left boundary (1-indexed)
     * @param r - Right boundary (1-indexed)
     * @returns Sum of A[l] + A[l+1] + ... + A[r]
     * 
     * Time Complexity: O(log n) - two prefix queries
     */
    rangeSum(l: number, r: number): number {
        // Handle edge cases
        if (l > r) return 0;
        if (l < 1) l = 1;
        if (r > this.n) r = this.n;
        
        // Range sum = prefix(r) - prefix(l-1)
        return this.prefixSum(r) - this.prefixSum(l - 1);
    }
 
    /**
     * Alternative: Query single element at index i.
     * This is a special case of range query where l = r.
     */
    getElement(i: number): number {
        return this.rangeSum(i, i);
    }
}
 
// Example usage
const bit = new FenwickTree(8);
// Suppose original array is [_, 1, 3, 5, 7, 9, 11, 13, 15]
// (index 0 unused, 1-indexed)
 
// After proper initialization...
console.log(bit.rangeSum(2, 5));  // Returns A[2] + A[3] + A[4] + A[5]
console.log(bit.rangeSum(1, 8));  // Returns entire array sum
console.log(bit.getElement(4));   // Returns just A[4]

Invertibility Requirement

The prefix-to-range trick ONLY works for invertible operations. For sum, we use subtraction. For XOR, we use XOR itself (self-inverse). But for MIN/MAX queries, prefix(r) - prefix(l-1) is meaningless — you cannot derive range minimum from prefix minimums. This is why BITs cannot handle min/max queries.

Edge Cases and Boundary Handling

Production code must handle edge cases gracefully. Let's examine common edge cases in BIT queries:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class RobustFenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        if (n < 0) throw new Error("Size must be non-negative");
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    query(i: number): number {
        // Edge case 1: i <= 0
        // Prefix sum of "nothing" is 0
        if (i <= 0) return 0;
        
        // Edge case 2: i > n
        // Query for entire array
        if (i > this.n) i = this.n;
        
        let sum = 0;
        while (i > 0) {
            sum += this.tree[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    rangeSum(l: number, r: number): number {
        // Edge case 3: Empty or invalid range
        if (l > r) return 0;
        
        // Edge case 4: l < 1 (clamp to valid range)
        if (l < 1) l = 1;
        
        // Edge case 5: r > n (clamp to valid range)
        if (r > this.n) r = this.n;
        
        // Edge case 6: After clamping, range might become invalid
        if (l > r) return 0;
        
        return this.query(r) - this.query(l - 1);
    }
 
    /**
     * Safe element access — returns 0 for out-of-bounds indices.
     */
    getElement(i: number): number {
        if (i < 1 || i > this.n) return 0;
        return this.rangeSum(i, i);
    }
}
 
// Edge case examples
const bit = new RobustFenwickTree(10);
 
// Edge cases for query
console.log(bit.query(0));   // Returns 0 (empty prefix)
console.log(bit.query(-5));  // Returns 0 (invalid index)
console.log(bit.query(100)); // Returns sum of all elements (clamped to n)
 
// Edge cases for rangeSum
console.log(bit.rangeSum(5, 3));   // Returns 0 (invalid range)
console.log(bit.rangeSum(-2, 5));  // Treated as rangeSum(1, 5)
console.log(bit.rangeSum(8, 100)); // Treated as rangeSum(8, 10)

Edge Case Summary
Edge Case	Input	Expected Behavior	Rationale
Zero index	query(0)	Return 0	Empty prefix sum
Negative index	query(-5)	Return 0	No elements before index 1
Beyond bounds	query(n+10)	Return query(n)	Maximum valid prefix
Empty range	rangeSum(5, 3)	Return 0	l > r is empty set
Single element	rangeSum(i, i)	Return A[i]	Range of length 1
Full range	rangeSum(1, n)	Return total sum	Entire array

Query Complexity Analysis

Let's rigorously analyze the time complexity of queries:

Time Complexity: O(log n)

Proof:

The query loop executes while i > 0, decrementing i by its lowest set bit each iteration.

Each iteration removes exactly one set bit from i
Any n-bit integer has at most n set bits
Since i ≤ n, we have at most ⌊log₂(n)⌋ + 1 bits
Therefore, at most ⌊log₂(n)⌋ + 1 iterations
Each iteration does O(1) work
Total: O(log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Empirically verify query complexity by counting iterations.
 */
function analyzeQueryComplexity(maxN: number): void {
    console.log("n\t\tMax Iterations\t\tlog₂(n)");
    console.log("─".repeat(50));
    
    for (let n = 1; n <= maxN; n *= 2) {
        let maxIterations = 0;
        
        for (let i = 1; i <= n; i++) {
            let iterations = 0;
            let j = i;
            
            while (j > 0) {
                iterations++;
                j -= j & (-j);
            }
            
            maxIterations = Math.max(maxIterations, iterations);
        }
        
        const logN = Math.floor(Math.log2(n)) + 1;
        console.log(`${n}\t\t${maxIterations}\t\t\t${logN}`);
    }
}
 
analyzeQueryComplexity(1048576);
 
/* Output:
n           Max Iterations      log₂(n)
──────────────────────────────────────────────────
1           1                   1
2           1                   2
4           2                   3
8           3                   4
16          4                   5
32          5                   6
64          6                   7
128         7                   8
256         8                   9
512         9                   10
1024        10                  11
...
1048576     20                  21
 
Confirmed: max iterations = ⌊log₂(n)⌋ + 1 = O(log n)
*/
 
/**
 * Average case analysis: Half the bits are set on average.
 */
function averageIterations(n: number): number {
    let totalIterations = 0;
    
    for (let i = 1; i <= n; i++) {
        let j = i;
        while (j > 0) {
            totalIterations++;
            j -= j & (-j);
        }
    }
    
    return totalIterations / n;
}
 
console.log(`Average iterations for n=1000000: ${averageIterations(1000000).toFixed(2)}`);
// Output: ~10.5, which is approximately log₂(n)/2

Best and Worst Cases

Best case: query(2^k) takes only 1 iteration (powers of 2 have one set bit) Worst case: query(2^k - 1) takes k iterations (all bits set) Average case: About log₂(n)/2 iterations (half the bits set on average)

XOR Queries — Another Invertible Operation

While sum is the most common operation, BITs work with any invertible operation. XOR is a perfect example because it's its own inverse: a ⊕ a = 0.

This enables:

Prefix XOR queries: XOR of elements from 1 to i
Range XOR queries: XOR of elements from l to r

Applications:

Finding single non-duplicate in stream
Cryptographic checksums
Error detection codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class XORFenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    /**
     * Toggle bit at index i with value.
     * For XOR, "update" means XOR-ing with a value.
     */
    update(i: number, value: number): void {
        while (i <= this.n) {
            this.tree[i] ^= value;
            i += i & (-i);
        }
    }
 
    /**
     * Get prefix XOR from 1 to i.
     */
    prefixXOR(i: number): number {
        let result = 0;
        while (i > 0) {
            result ^= this.tree[i];
            i -= i & (-i);
        }
        return result;
    }
 
    /**
     * Get range XOR from l to r.
     * Works because XOR is self-inverse: (a ⊕ b) ⊕ a = b
     */
    rangeXOR(l: number, r: number): number {
        if (l > r) return 0;
        return this.prefixXOR(r) ^ this.prefixXOR(l - 1);
    }
}
 
// Example: Find XOR of range under dynamic updates
const xorBit = new XORFenwickTree(8);
 
// Insert values: [3, 1, 4, 1, 5, 9, 2, 6]
[3, 1, 4, 1, 5, 9, 2, 6].forEach((val, idx) => {
    xorBit.update(idx + 1, val);  // 1-indexed
});
 
console.log(xorBit.prefixXOR(4));   // 3 ^ 1 ^ 4 ^ 1 = 7
console.log(xorBit.rangeXOR(2, 5)); // 1 ^ 4 ^ 1 ^ 5 = 1
 
// Update: change position 3 from 4 to 7
// XOR with 4 to remove old value, XOR with 7 to add new
xorBit.update(3, 4 ^ 7);  // Equivalent to: remove 4, add 7

Generalization: Group Operations

BITs work with any operation that forms an Abelian group: associative, commutative, has identity, and every element has an inverse. Sum (with subtraction), XOR (self-inverse), and multiplication mod prime (with modular inverse) all qualify. Max/min do not because there's no inverse.

Frequency and Counting Queries

A powerful application of prefix queries is frequency counting — answering questions like "how many elements less than x have been seen?"

The Pattern:

Create a BIT where index i represents value i
BIT[i] = count of times value i has appeared
prefix(x) = count of elements ≤ x
rangeSum(a, b) = count of elements in [a, b]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class FrequencyBIT {
    private bit: number[];
    private maxValue: number;
 
    constructor(maxValue: number) {
        this.maxValue = maxValue;
        this.bit = new Array(maxValue + 1).fill(0);
    }
 
    private update(i: number, delta: number): void {
        while (i <= this.maxValue) {
            this.bit[i] += delta;
            i += i & (-i);
        }
    }
 
    private prefixCount(i: number): number {
        if (i <= 0) return 0;
        if (i > this.maxValue) i = this.maxValue;
        
        let count = 0;
        while (i > 0) {
            count += this.bit[i];
            i -= i & (-i);
        }
        return count;
    }
 
    /**
     * Add an element with given value.
     */
    add(value: number): void {
        if (value >= 1 && value <= this.maxValue) {
            this.update(value, 1);
        }
    }
 
    /**
     * Remove an element with given value.
     */
    remove(value: number): void {
        if (value >= 1 && value <= this.maxValue) {
            this.update(value, -1);
        }
    }
 
    /**
     * Count elements less than or equal to value.
     */
    countLessOrEqual(value: number): number {
        return this.prefixCount(value);
    }
 
    /**
     * Count elements strictly less than value.
     */
    countLess(value: number): number {
        return this.prefixCount(value - 1);
    }
 
    /**
     * Count elements in range [low, high].
     */
    countInRange(low: number, high: number): number {
        return this.prefixCount(high) - this.prefixCount(low - 1);
    }
 
    /**
     * Find rank of a value (1-indexed position if sorted).
     */
    getRank(value: number): number {
        return this.prefixCount(value);
    }
}
 
// Example: Online rank calculation
const freq = new FrequencyBIT(100);  // Values from 1 to 100
 
// Stream of values arrives
[45, 23, 67, 12, 45, 89, 23, 34].forEach(v => freq.add(v));
 
console.log(freq.countLessOrEqual(50));  // Count elements ≤ 50
console.log(freq.countInRange(20, 50));  // Count elements in [20, 50]
console.log(freq.getRank(45));           // How many elements ≤ 45?
 
// Remove an element
freq.remove(23);
console.log(freq.countLessOrEqual(30));  // Updated count

Classic Application: Inversion Count

An inversion is a pair (i, j) where i < j but A[i] > A[j]. Counting inversions measures how "unsorted" an array is.

Algorithm:

Process array from right to left
For each element A[i], count elements already seen that are smaller
Each such element forms an inversion with A[i]
Add A[i] to the frequency BIT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
function countInversions(arr: number[]): number {
    if (arr.length <= 1) return 0;
    
    // Coordinate compression: map values to 1..n
    const sorted = [...arr].sort((a, b) => a - b);
    const rankMap = new Map<number, number>();
    let rank = 1;
    for (const val of sorted) {
        if (!rankMap.has(val)) {
            rankMap.set(val, rank++);
        }
    }
    
    const n = rankMap.size;
    const bit = new Array(n + 1).fill(0);
    
    const update = (i: number) => {
        while (i <= n) {
            bit[i]++;
            i += i & (-i);
        }
    };
    
    const query = (i: number): number => {
        let sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= i & (-i);
        }
        return sum;
    };
    
    let inversions = 0;
    
    // Process from right to left
    for (let i = arr.length - 1; i >= 0; i--) {
        const r = rankMap.get(arr[i])!;
        
        // Count elements smaller than current (those already in BIT)
        inversions += query(r - 1);
        
        // Add current element to BIT
        update(r);
    }
    
    return inversions;
}
 
// Example
console.log(countInversions([2, 4, 1, 3, 5])); // 3 inversions: (2,1), (4,1), (4,3)
console.log(countInversions([5, 4, 3, 2, 1])); // 10 inversions (reverse sorted)
console.log(countInversions([1, 2, 3, 4, 5])); // 0 inversions (already sorted)

Binary Search on BIT — Finding k-th Element

A powerful technique combines BIT queries with binary search to find the k-th smallest element in a dynamic multiset.

Problem: Given a multiset with frequent insertions and deletions, efficiently find the k-th smallest element.

Key Insight: If BIT[i] stores the frequency of value i, then prefix(x) = count of elements ≤ x. We can binary search for the smallest x where prefix(x) ≥ k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class DynamicOrderStatistics {
    private bit: number[];
    private maxValue: number;
 
    constructor(maxValue: number) {
        this.maxValue = maxValue;
        this.bit = new Array(maxValue + 1).fill(0);
    }
 
    private update(i: number, delta: number): void {
        while (i <= this.maxValue) {
            this.bit[i] += delta;
            i += i & (-i);
        }
    }
 
    private query(i: number): number {
        let sum = 0;
        while (i > 0) {
            sum += this.bit[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    add(value: number): void {
        this.update(value, 1);
    }
 
    remove(value: number): void {
        this.update(value, -1);
    }
 
    /**
     * Find the k-th smallest element (1-indexed).
     * Uses binary search on prefix sums.
     * 
     * Time Complexity: O(log² n) — binary search with O(log n) queries
     */
    kthSmallest(k: number): number {
        let lo = 1;
        let hi = this.maxValue;
        
        while (lo < hi) {
            const mid = Math.floor((lo + hi) / 2);
            
            if (this.query(mid) < k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return this.query(lo) >= k ? lo : -1;  // -1 if k is too large
    }
 
    /**
     * Optimized: O(log n) k-th element using bit descent.
     * This clever technique descends through the BIT structure directly.
     */
    kthSmallestOptimal(k: number): number {
        let pos = 0;
        let bitMask = this.highestPowerOf2(this.maxValue);
        
        while (bitMask > 0) {
            const next = pos + bitMask;
            
            if (next <= this.maxValue && this.bit[next] < k) {
                pos = next;
                k -= this.bit[next];
            }
            
            bitMask >>= 1;
        }
        
        return pos + 1;  // 1-indexed result
    }
 
    private highestPowerOf2(n: number): number {
        let p = 1;
        while (p * 2 <= n) p *= 2;
        return p;
    }
}
 
// Example usage
const stats = new DynamicOrderStatistics(100);
 
// Add elements: multiset {10, 20, 15, 20, 30}
[10, 20, 15, 20, 30].forEach(v => stats.add(v));
 
console.log(stats.kthSmallest(1));  // 10 (smallest)
console.log(stats.kthSmallest(2));  // 15 (2nd smallest)
console.log(stats.kthSmallest(3));  // 20 (3rd smallest)
console.log(stats.kthSmallest(4));  // 20 (there are two 20s)
console.log(stats.kthSmallest(5));  // 30 (largest)
 
// Remove one 20
stats.remove(20);
console.log(stats.kthSmallest(3));  // Now 20 (only one left)
console.log(stats.kthSmallest(4));  // Now 30

Two Complexity Options

Standard binary search: O(log² n) — simple to understand and implement BIT descent technique: O(log n) — uses the BIT structure to descend directly, examining each "level" once

For most applications, the O(log² n) version is sufficient and less error-prone.

Summary — Mastering BIT Queries

This page provided comprehensive coverage of prefix sum queries in Fenwick Trees. Here are the key takeaways:

Key Takeaways

•Query algorithm strips the lowest set bit repeatedly (i -= i & -i), collecting disjoint ranges.
•Iterations equal popcount(i) — the number of set bits in i, which is at most O(log n).
•Range queries derive from prefix queries: sum(l, r) = prefix(r) - prefix(l - 1).
•Edge cases (i ≤ 0, i > n, invalid ranges) must be handled for production code.
•XOR queries work identically because XOR is invertible (self-inverse).
•Frequency BITs enable counting queries: elements less than x, elements in range [a, b].
•k-th element can be found via binary search on prefix sums in O(log² n) or O(log n) with BIT descent.

What's next:

With queries mastered, we turn to the other fundamental operation: point updates. The next page examines how to efficiently update individual elements while maintaining the BIT invariant.

Page Complete

You now have deep mastery of BIT queries — from basic prefix sums to advanced applications like frequency counting, inversion detection, and order statistics. You can implement robust query operations and recognize problems where BIT queries provide elegant solutions.

3 / 5

Loading learning content...

Data Structures & AlgorithmsFenwick Trees (Binary Indexed Trees)

Fenwick Trees — Binary Indexed Trees

LevelAdvanced

Duration90 mins

TopicFenwick Trees (Binary Indexed Trees)

3 / 5

Prefix Sum Queries

Querying Cumulative Sums Efficiently

This seemingly simple operation is the foundation for a wide range of applications. From this single primitive, we can derive:

Range sum queries: Sum of elements in any arbitrary range [l, r]
Frequency queries: Count of elements with certain properties
Running totals: Cumulative statistics up to any point
Order statistics: Finding ranks and quantiles

This page examines the query operation in exhaustive detail — the algorithm, its correctness, variations, optimizations, and practical applications.

What You Will Learn

The Query Algorithm — Step by Step

Let's formalize the query algorithm and trace through its execution in complete detail.

The Query Goal:

Given an index i (1-indexed), compute:

prefix(i) = A[1] + A[2] + ... + A[i]

The Algorithm:

function query(i):
    sum = 0
    while i > 0:
        sum = sum + BIT[i]
        i = i - (i & -i)    // Remove lowest set bit
    return sum

Why it works:

Recall that BIT[i] stores the sum of elements in the range [i - LSB(i) + 1, i]. The query algorithm collects these non-overlapping ranges by repeatedly stripping the lowest set bit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class FenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    /**
     * Query prefix sum from index 1 to i (inclusive).
     * 
     * @param i - The ending index (1-indexed)
     * @returns The sum A[1] + A[2] + ... + A[i]
     * 
     * Preconditions:
     *   - 1 <= i <= n
     *   - BIT invariant is maintained
     * 
     * Postconditions:
     *   - Returns the exact prefix sum
     *   - BIT is not modified
     */
    query(i: number): number {
        // Validate input
        if (i < 0) return 0;
        if (i > this.n) i = this.n;
        
        let sum = 0;
        
        while (i > 0) {
            sum += this.tree[i];
            i -= i & (-i);  // Remove lowest set bit
        }
        
        return sum;
    }
 
    /**
     * Query with detailed tracing for educational purposes.
     * Returns both the sum and the trace of indices visited.
     */
    queryWithTrace(i: number): { sum: number; trace: number[] } {
        const trace: number[] = [];
        let sum = 0;
        
        while (i > 0) {
            trace.push(i);
            sum += this.tree[i];
            i -= i & (-i);
        }
        
        return { sum, trace };
    }
}
 
// Example usage with trace
const bit = new FenwickTree(16);
// Assume BIT is populated...
 
// Query for i = 13 (binary: 1101)
const result = bit.queryWithTrace(13);
console.log("Indices visited:", result.trace);
// Output: [13, 12, 8]
// 13 (1101) -> 12 (1100) -> 8 (1000) -> 0 (stop)
 
// Query for i = 15 (binary: 1111)
const result2 = bit.queryWithTrace(15);
console.log("Indices visited:", result2.trace);
// Output: [15, 14, 12, 8]
// Visits 4 indices because 15 has 4 set bits

Iteration Count = popcount(i)

Complete Trace Examples

Let's trace the query algorithm for several inputs to build deep intuition:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Query prefix(7):
 
i = 7 (binary: 0111)
├── LSB(7) = 1
├── BIT[7] covers range [7, 7]
├── Add BIT[7] to sum
└── Next: i = 7 - 1 = 6
 
i = 6 (binary: 0110)
├── LSB(6) = 2
├── BIT[6] covers range [5, 6]
├── Add BIT[6] to sum
└── Next: i = 6 - 2 = 4
 
i = 4 (binary: 0100)
├── LSB(4) = 4
├── BIT[4] covers range [1, 4]
├── Add BIT[4] to sum
└── Next: i = 4 - 4 = 0
 
i = 0: STOP
 
Result: BIT[7] + BIT[6] + BIT[4]
      = A[7] + (A[5]+A[6]) + (A[1]+A[2]+A[3]+A[4])
      = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] ✓
 
Iterations: 3 (popcount of 7 = 3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Query prefix(16):
 
i = 16 (binary: 10000)
├── LSB(16) = 16
├── BIT[16] covers range [1, 16]
├── Add BIT[16] to sum
└── Next: i = 16 - 16 = 0
 
i = 0: STOP
 
Result: BIT[16]
      = A[1] + A[2] + ... + A[16] ✓
 
Iterations: 1 (popcount of 16 = 1)
 
This is the best case! Powers of 2 require only ONE access.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Query prefix(11):
 
i = 11 (binary: 1011)
├── LSB(11) = 1
├── BIT[11] covers range [11, 11]
├── Add BIT[11] to sum
└── Next: i = 11 - 1 = 10
 
i = 10 (binary: 1010)
├── LSB(10) = 2
├── BIT[10] covers range [9, 10]
├── Add BIT[10] to sum
└── Next: i = 10 - 2 = 8
 
i = 8 (binary: 1000)
├── LSB(8) = 8
├── BIT[8] covers range [1, 8]
├── Add BIT[8] to sum
└── Next: i = 8 - 8 = 0
 
i = 0: STOP
 
Result: BIT[11] + BIT[10] + BIT[8]
      = A[11] + (A[9]+A[10]) + (A[1]+...+A[8])
      = A[1] + A[2] + ... + A[11] ✓
 
Iterations: 3

Query Iterations by Index
Index i	Binary	popcount	Indices Visited	Ranges Collected
1	0001	1	[1]	[1..1]
4	0100	1	[4]	[1..4]
7	0111	3	[7, 6, 4]	[7..7], [5..6], [1..4]
8	1000	1	[8]	[1..8]
10	1010	2	[10, 8]	[9..10], [1..8]
15	1111	4	[15, 14, 12, 8]	[15], [13..14], [9..12], [1..8]
16	10000	1	[16]	[1..16]

Range Queries from Prefix Queries

While BITs natively support prefix queries, we often need range queries: the sum of elements in an arbitrary range [l, r].

The Key Insight:

For any invertible operation (where we can "subtract" to undo), range queries reduce to prefix queries:

sum(l, r) = prefix(r) - prefix(l - 1)

Visual Explanation:

Array:    [A₁] [A₂] [A₃] [A₄] [A₅] [A₆] [A₇] [A₈]

prefix(r) = A₁ + A₂ + ... + Aₗ₋₁ + Aₗ + ... + Aᵣ
prefix(l-1) = A₁ + A₂ + ... + Aₗ₋₁

Subtraction cancels the common prefix:
sum(l, r) = Aₗ + ... + Aᵣ ✓

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class FenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    // Prefix sum query
    private prefixSum(i: number): number {
        if (i <= 0) return 0;
        if (i > this.n) i = this.n;
        
        let sum = 0;
        while (i > 0) {
            sum += this.tree[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    /**
     * Query the sum of elements in range [l, r] (1-indexed, inclusive).
     * 
     * @param l - Left boundary (1-indexed)
     * @param r - Right boundary (1-indexed)
     * @returns Sum of A[l] + A[l+1] + ... + A[r]
     * 
     * Time Complexity: O(log n) - two prefix queries
     */
    rangeSum(l: number, r: number): number {
        // Handle edge cases
        if (l > r) return 0;
        if (l < 1) l = 1;
        if (r > this.n) r = this.n;
        
        // Range sum = prefix(r) - prefix(l-1)
        return this.prefixSum(r) - this.prefixSum(l - 1);
    }
 
    /**
     * Alternative: Query single element at index i.
     * This is a special case of range query where l = r.
     */
    getElement(i: number): number {
        return this.rangeSum(i, i);
    }
}
 
// Example usage
const bit = new FenwickTree(8);
// Suppose original array is [_, 1, 3, 5, 7, 9, 11, 13, 15]
// (index 0 unused, 1-indexed)
 
// After proper initialization...
console.log(bit.rangeSum(2, 5));  // Returns A[2] + A[3] + A[4] + A[5]
console.log(bit.rangeSum(1, 8));  // Returns entire array sum
console.log(bit.getElement(4));   // Returns just A[4]

Invertibility Requirement

Edge Cases and Boundary Handling

Production code must handle edge cases gracefully. Let's examine common edge cases in BIT queries:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class RobustFenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        if (n < 0) throw new Error("Size must be non-negative");
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    query(i: number): number {
        // Edge case 1: i <= 0
        // Prefix sum of "nothing" is 0
        if (i <= 0) return 0;
        
        // Edge case 2: i > n
        // Query for entire array
        if (i > this.n) i = this.n;
        
        let sum = 0;
        while (i > 0) {
            sum += this.tree[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    rangeSum(l: number, r: number): number {
        // Edge case 3: Empty or invalid range
        if (l > r) return 0;
        
        // Edge case 4: l < 1 (clamp to valid range)
        if (l < 1) l = 1;
        
        // Edge case 5: r > n (clamp to valid range)
        if (r > this.n) r = this.n;
        
        // Edge case 6: After clamping, range might become invalid
        if (l > r) return 0;
        
        return this.query(r) - this.query(l - 1);
    }
 
    /**
     * Safe element access — returns 0 for out-of-bounds indices.
     */
    getElement(i: number): number {
        if (i < 1 || i > this.n) return 0;
        return this.rangeSum(i, i);
    }
}
 
// Edge case examples
const bit = new RobustFenwickTree(10);
 
// Edge cases for query
console.log(bit.query(0));   // Returns 0 (empty prefix)
console.log(bit.query(-5));  // Returns 0 (invalid index)
console.log(bit.query(100)); // Returns sum of all elements (clamped to n)
 
// Edge cases for rangeSum
console.log(bit.rangeSum(5, 3));   // Returns 0 (invalid range)
console.log(bit.rangeSum(-2, 5));  // Treated as rangeSum(1, 5)
console.log(bit.rangeSum(8, 100)); // Treated as rangeSum(8, 10)

Edge Case Summary
Edge Case	Input	Expected Behavior	Rationale
Zero index	query(0)	Return 0	Empty prefix sum
Negative index	query(-5)	Return 0	No elements before index 1
Beyond bounds	query(n+10)	Return query(n)	Maximum valid prefix
Empty range	rangeSum(5, 3)	Return 0	l > r is empty set
Single element	rangeSum(i, i)	Return A[i]	Range of length 1
Full range	rangeSum(1, n)	Return total sum	Entire array

Query Complexity Analysis

Let's rigorously analyze the time complexity of queries:

Time Complexity: O(log n)

Proof:

The query loop executes while i > 0, decrementing i by its lowest set bit each iteration.

Each iteration removes exactly one set bit from i
Any n-bit integer has at most n set bits
Since i ≤ n, we have at most ⌊log₂(n)⌋ + 1 bits
Therefore, at most ⌊log₂(n)⌋ + 1 iterations
Each iteration does O(1) work
Total: O(log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Empirically verify query complexity by counting iterations.
 */
function analyzeQueryComplexity(maxN: number): void {
    console.log("n\t\tMax Iterations\t\tlog₂(n)");
    console.log("─".repeat(50));
    
    for (let n = 1; n <= maxN; n *= 2) {
        let maxIterations = 0;
        
        for (let i = 1; i <= n; i++) {
            let iterations = 0;
            let j = i;
            
            while (j > 0) {
                iterations++;
                j -= j & (-j);
            }
            
            maxIterations = Math.max(maxIterations, iterations);
        }
        
        const logN = Math.floor(Math.log2(n)) + 1;
        console.log(`${n}\t\t${maxIterations}\t\t\t${logN}`);
    }
}
 
analyzeQueryComplexity(1048576);
 
/* Output:
n           Max Iterations      log₂(n)
──────────────────────────────────────────────────
1           1                   1
2           1                   2
4           2                   3
8           3                   4
16          4                   5
32          5                   6
64          6                   7
128         7                   8
256         8                   9
512         9                   10
1024        10                  11
...
1048576     20                  21
 
Confirmed: max iterations = ⌊log₂(n)⌋ + 1 = O(log n)
*/
 
/**
 * Average case analysis: Half the bits are set on average.
 */
function averageIterations(n: number): number {
    let totalIterations = 0;
    
    for (let i = 1; i <= n; i++) {
        let j = i;
        while (j > 0) {
            totalIterations++;
            j -= j & (-j);
        }
    }
    
    return totalIterations / n;
}
 
console.log(`Average iterations for n=1000000: ${averageIterations(1000000).toFixed(2)}`);
// Output: ~10.5, which is approximately log₂(n)/2

Best and Worst Cases

XOR Queries — Another Invertible Operation

While sum is the most common operation, BITs work with any invertible operation. XOR is a perfect example because it's its own inverse: a ⊕ a = 0.

This enables:

Prefix XOR queries: XOR of elements from 1 to i
Range XOR queries: XOR of elements from l to r

Applications:

Finding single non-duplicate in stream
Cryptographic checksums
Error detection codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class XORFenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    /**
     * Toggle bit at index i with value.
     * For XOR, "update" means XOR-ing with a value.
     */
    update(i: number, value: number): void {
        while (i <= this.n) {
            this.tree[i] ^= value;
            i += i & (-i);
        }
    }
 
    /**
     * Get prefix XOR from 1 to i.
     */
    prefixXOR(i: number): number {
        let result = 0;
        while (i > 0) {
            result ^= this.tree[i];
            i -= i & (-i);
        }
        return result;
    }
 
    /**
     * Get range XOR from l to r.
     * Works because XOR is self-inverse: (a ⊕ b) ⊕ a = b
     */
    rangeXOR(l: number, r: number): number {
        if (l > r) return 0;
        return this.prefixXOR(r) ^ this.prefixXOR(l - 1);
    }
}
 
// Example: Find XOR of range under dynamic updates
const xorBit = new XORFenwickTree(8);
 
// Insert values: [3, 1, 4, 1, 5, 9, 2, 6]
[3, 1, 4, 1, 5, 9, 2, 6].forEach((val, idx) => {
    xorBit.update(idx + 1, val);  // 1-indexed
});
 
console.log(xorBit.prefixXOR(4));   // 3 ^ 1 ^ 4 ^ 1 = 7
console.log(xorBit.rangeXOR(2, 5)); // 1 ^ 4 ^ 1 ^ 5 = 1
 
// Update: change position 3 from 4 to 7
// XOR with 4 to remove old value, XOR with 7 to add new
xorBit.update(3, 4 ^ 7);  // Equivalent to: remove 4, add 7

Generalization: Group Operations

Frequency and Counting Queries

A powerful application of prefix queries is frequency counting — answering questions like "how many elements less than x have been seen?"

The Pattern:

Create a BIT where index i represents value i
BIT[i] = count of times value i has appeared
prefix(x) = count of elements ≤ x
rangeSum(a, b) = count of elements in [a, b]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class FrequencyBIT {
    private bit: number[];
    private maxValue: number;
 
    constructor(maxValue: number) {
        this.maxValue = maxValue;
        this.bit = new Array(maxValue + 1).fill(0);
    }
 
    private update(i: number, delta: number): void {
        while (i <= this.maxValue) {
            this.bit[i] += delta;
            i += i & (-i);
        }
    }
 
    private prefixCount(i: number): number {
        if (i <= 0) return 0;
        if (i > this.maxValue) i = this.maxValue;
        
        let count = 0;
        while (i > 0) {
            count += this.bit[i];
            i -= i & (-i);
        }
        return count;
    }
 
    /**
     * Add an element with given value.
     */
    add(value: number): void {
        if (value >= 1 && value <= this.maxValue) {
            this.update(value, 1);
        }
    }
 
    /**
     * Remove an element with given value.
     */
    remove(value: number): void {
        if (value >= 1 && value <= this.maxValue) {
            this.update(value, -1);
        }
    }
 
    /**
     * Count elements less than or equal to value.
     */
    countLessOrEqual(value: number): number {
        return this.prefixCount(value);
    }
 
    /**
     * Count elements strictly less than value.
     */
    countLess(value: number): number {
        return this.prefixCount(value - 1);
    }
 
    /**
     * Count elements in range [low, high].
     */
    countInRange(low: number, high: number): number {
        return this.prefixCount(high) - this.prefixCount(low - 1);
    }
 
    /**
     * Find rank of a value (1-indexed position if sorted).
     */
    getRank(value: number): number {
        return this.prefixCount(value);
    }
}
 
// Example: Online rank calculation
const freq = new FrequencyBIT(100);  // Values from 1 to 100
 
// Stream of values arrives
[45, 23, 67, 12, 45, 89, 23, 34].forEach(v => freq.add(v));
 
console.log(freq.countLessOrEqual(50));  // Count elements ≤ 50
console.log(freq.countInRange(20, 50));  // Count elements in [20, 50]
console.log(freq.getRank(45));           // How many elements ≤ 45?
 
// Remove an element
freq.remove(23);
console.log(freq.countLessOrEqual(30));  // Updated count

Classic Application: Inversion Count

An inversion is a pair (i, j) where i < j but A[i] > A[j]. Counting inversions measures how "unsorted" an array is.

Algorithm:

Process array from right to left
For each element A[i], count elements already seen that are smaller
Each such element forms an inversion with A[i]
Add A[i] to the frequency BIT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
function countInversions(arr: number[]): number {
    if (arr.length <= 1) return 0;
    
    // Coordinate compression: map values to 1..n
    const sorted = [...arr].sort((a, b) => a - b);
    const rankMap = new Map<number, number>();
    let rank = 1;
    for (const val of sorted) {
        if (!rankMap.has(val)) {
            rankMap.set(val, rank++);
        }
    }
    
    const n = rankMap.size;
    const bit = new Array(n + 1).fill(0);
    
    const update = (i: number) => {
        while (i <= n) {
            bit[i]++;
            i += i & (-i);
        }
    };
    
    const query = (i: number): number => {
        let sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= i & (-i);
        }
        return sum;
    };
    
    let inversions = 0;
    
    // Process from right to left
    for (let i = arr.length - 1; i >= 0; i--) {
        const r = rankMap.get(arr[i])!;
        
        // Count elements smaller than current (those already in BIT)
        inversions += query(r - 1);
        
        // Add current element to BIT
        update(r);
    }
    
    return inversions;
}
 
// Example
console.log(countInversions([2, 4, 1, 3, 5])); // 3 inversions: (2,1), (4,1), (4,3)
console.log(countInversions([5, 4, 3, 2, 1])); // 10 inversions (reverse sorted)
console.log(countInversions([1, 2, 3, 4, 5])); // 0 inversions (already sorted)

Binary Search on BIT — Finding k-th Element

A powerful technique combines BIT queries with binary search to find the k-th smallest element in a dynamic multiset.

Problem: Given a multiset with frequent insertions and deletions, efficiently find the k-th smallest element.

Key Insight: If BIT[i] stores the frequency of value i, then prefix(x) = count of elements ≤ x. We can binary search for the smallest x where prefix(x) ≥ k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class DynamicOrderStatistics {
    private bit: number[];
    private maxValue: number;
 
    constructor(maxValue: number) {
        this.maxValue = maxValue;
        this.bit = new Array(maxValue + 1).fill(0);
    }
 
    private update(i: number, delta: number): void {
        while (i <= this.maxValue) {
            this.bit[i] += delta;
            i += i & (-i);
        }
    }
 
    private query(i: number): number {
        let sum = 0;
        while (i > 0) {
            sum += this.bit[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    add(value: number): void {
        this.update(value, 1);
    }
 
    remove(value: number): void {
        this.update(value, -1);
    }
 
    /**
     * Find the k-th smallest element (1-indexed).
     * Uses binary search on prefix sums.
     * 
     * Time Complexity: O(log² n) — binary search with O(log n) queries
     */
    kthSmallest(k: number): number {
        let lo = 1;
        let hi = this.maxValue;
        
        while (lo < hi) {
            const mid = Math.floor((lo + hi) / 2);
            
            if (this.query(mid) < k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return this.query(lo) >= k ? lo : -1;  // -1 if k is too large
    }
 
    /**
     * Optimized: O(log n) k-th element using bit descent.
     * This clever technique descends through the BIT structure directly.
     */
    kthSmallestOptimal(k: number): number {
        let pos = 0;
        let bitMask = this.highestPowerOf2(this.maxValue);
        
        while (bitMask > 0) {
            const next = pos + bitMask;
            
            if (next <= this.maxValue && this.bit[next] < k) {
                pos = next;
                k -= this.bit[next];
            }
            
            bitMask >>= 1;
        }
        
        return pos + 1;  // 1-indexed result
    }
 
    private highestPowerOf2(n: number): number {
        let p = 1;
        while (p * 2 <= n) p *= 2;
        return p;
    }
}
 
// Example usage
const stats = new DynamicOrderStatistics(100);
 
// Add elements: multiset {10, 20, 15, 20, 30}
[10, 20, 15, 20, 30].forEach(v => stats.add(v));
 
console.log(stats.kthSmallest(1));  // 10 (smallest)
console.log(stats.kthSmallest(2));  // 15 (2nd smallest)
console.log(stats.kthSmallest(3));  // 20 (3rd smallest)
console.log(stats.kthSmallest(4));  // 20 (there are two 20s)
console.log(stats.kthSmallest(5));  // 30 (largest)
 
// Remove one 20
stats.remove(20);
console.log(stats.kthSmallest(3));  // Now 20 (only one left)
console.log(stats.kthSmallest(4));  // Now 30

Two Complexity Options

Standard binary search: O(log² n) — simple to understand and implement BIT descent technique: O(log n) — uses the BIT structure to descend directly, examining each "level" once

For most applications, the O(log² n) version is sufficient and less error-prone.

Summary — Mastering BIT Queries

This page provided comprehensive coverage of prefix sum queries in Fenwick Trees. Here are the key takeaways:

Key Takeaways

•Query algorithm strips the lowest set bit repeatedly (i -= i & -i), collecting disjoint ranges.
•Iterations equal popcount(i) — the number of set bits in i, which is at most O(log n).
•Range queries derive from prefix queries: sum(l, r) = prefix(r) - prefix(l - 1).
•Edge cases (i ≤ 0, i > n, invalid ranges) must be handled for production code.
•XOR queries work identically because XOR is invertible (self-inverse).
•Frequency BITs enable counting queries: elements less than x, elements in range [a, b].
•k-th element can be found via binary search on prefix sums in O(log² n) or O(log n) with BIT descent.

What's next:

With queries mastered, we turn to the other fundamental operation: point updates. The next page examines how to efficiently update individual elements while maintaining the BIT invariant.

Page Complete

3 / 5