Data Structures & AlgorithmsFenwick Trees (Binary Indexed Trees)

Fenwick Trees — Binary Indexed Trees

LevelAdvanced

Duration90 mins

TopicFenwick Trees (Binary Indexed Trees)

4 / 5

Point Updates

Dynamic Data — The Power of Updates

A prefix sum array could answer range queries in O(1) time — far better than BIT's O(log n). So why use a Fenwick Tree?

The answer lies in updates. A static prefix sum array requires O(n) time to update a single element (every prefix sum after that element must be recalculated). Fenwick Trees achieve O(log n) updates while maintaining O(log n) queries — a dramatically better trade-off for dynamic data.

This page examines point updates in complete detail: the algorithm, its mechanics, the relationship between updates and queries, and advanced patterns for handling range updates.

What You Will Learn

By the end of this page, you will: • Master the point update algorithm and understand why it works • See the beautiful symmetry between updates and queries • Trace update propagation through the BIT structure • Handle edge cases in production update code • Implement range updates using the difference array technique • Build a complete, robust Fenwick Tree implementation

The Update Algorithm — Step by Step

The update operation adds a value (delta) to an element at a given index. After the update, all future queries must reflect this change.

The Update Goal:

Given an index i and a value delta, perform:

A[i] = A[i] + delta

And update the BIT so all future prefix queries are correct.

The Algorithm:

function update(i, delta):
    while i <= n:
        BIT[i] = BIT[i] + delta
        i = i + (i & -i)    // Add lowest set bit

Why it works:

Every BIT index j whose range includes position i must be updated. The algorithm finds these indices by starting at i and repeatedly adding the LSB, which moves to the next "covering" index.

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
class FenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    /**
     * Add delta to the element at index i.
     * 
     * @param i - The index to update (1-indexed)
     * @param delta - The value to add (can be negative)
     * 
     * Preconditions:
     *   - 1 <= i <= n
     * 
     * Postconditions:
     *   - All BIT entries covering index i are updated
     *   - Future queries will reflect the change
     * 
     * Time Complexity: O(log n)
     */
    update(i: number, delta: number): void {
        // Validate input
        if (i < 1 || i > this.n) {
            throw new Error(`Index ${i} out of bounds [1, ${this.n}]`);
        }
        
        // Propagate update to all covering indices
        while (i <= this.n) {
            this.tree[i] += delta;
            i += i & (-i);  // Add lowest set bit
        }
    }
 
    /**
     * Update with detailed tracing for educational purposes.
     */
    updateWithTrace(i: number, delta: number): number[] {
        const trace: number[] = [];
        
        while (i <= this.n) {
            trace.push(i);
            this.tree[i] += delta;
            i += i & (-i);
        }
        
        return trace;
    }
}
 
// Example with tracing
const bit = new FenwickTree(16);
 
// Update position 3 with delta = 5
const trace = bit.updateWithTrace(3, 5);
console.log("Indices updated:", trace);
// Output: [3, 4, 8, 16]
// 3 (0011) → +1 → 4 (0100) → +4 → 8 (1000) → +8 → 16 (10000) → done
 
// Update position 7 with delta = 10
const trace2 = bit.updateWithTrace(7, 10);
console.log("Indices updated:", trace2);
// Output: [7, 8, 16]

Add vs Subtract LSB

Query subtracts the LSB: i -= i & (-i) — moves to previous disjoint range Update adds the LSB: i += i & (-i) — moves to next covering index

These are complementary operations that traverse the implicit tree in opposite directions.

Complete Trace Examples

Let's trace the update algorithm for several inputs to build deep intuition about propagation:

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
Update(1, 5):
 
i = 1 (binary: 0001)
├── LSB(1) = 1
├── BIT[1] covers [1..1] — includes position 1 ✓
├── BIT[1] += 5
└── Next: i = 1 + 1 = 2
 
i = 2 (binary: 0010)
├── LSB(2) = 2
├── BIT[2] covers [1..2] — includes position 1 ✓
├── BIT[2] += 5
└── Next: i = 2 + 2 = 4
 
i = 4 (binary: 0100)
├── LSB(4) = 4
├── BIT[4] covers [1..4] — includes position 1 ✓
├── BIT[4] += 5
└── Next: i = 4 + 4 = 8
 
i = 8 (binary: 1000)
├── LSB(8) = 8
├── BIT[8] covers [1..8] — includes position 1 ✓
├── BIT[8] += 5
└── Next: i = 8 + 8 = 16
 
i = 16 (binary: 10000)
├── LSB(16) = 16
├── BIT[16] covers [1..16] — includes position 1 ✓
├── BIT[16] += 5
└── Next: i = 16 + 16 = 32 > n, STOP
 
Indices updated: [1, 2, 4, 8, 16]
All ranges covering position 1 were updated correctly!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Update(5, 7):
 
i = 5 (binary: 0101)
├── LSB(5) = 1
├── BIT[5] covers [5..5] — includes position 5 ✓
├── BIT[5] += 7
└── Next: i = 5 + 1 = 6
 
i = 6 (binary: 0110)
├── LSB(6) = 2
├── BIT[6] covers [5..6] — includes position 5 ✓
├── BIT[6] += 7
└── Next: i = 6 + 2 = 8
 
i = 8 (binary: 1000)
├── LSB(8) = 8
├── BIT[8] covers [1..8] — includes position 5 ✓
├── BIT[8] += 7
└── Next: i = 8 + 8 = 16
 
i = 16 (beyond n=8 in this example), STOP
 
Indices updated: [5, 6, 8]
Exactly the indices whose ranges include position 5!

Update Propagation Paths (for n = 16)
Position i	Binary	Indices Updated	Count
1	00001	1, 2, 4, 8, 16	5
3	00011	3, 4, 8, 16	4
4	00100	4, 8, 16	3
5	00101	5, 6, 8, 16	4
7	00111	7, 8, 16	3
8	01000	8, 16	2
10	01010	10, 12, 16	3
12	01100	12, 16	2
15	01111	15, 16	2
16	10000	16	1

Iteration Count Pattern

The number of indices updated for position i is the number of "levels" above i in the implicit tree. This is related to the number of trailing zeros in i's binary representation plus the remaining bits until n. In all cases, it's O(log n).

The Symmetry Between Updates and Queries

There's a beautiful symmetry in how queries and updates traverse the BIT:

Query (prefix sum):

Starts at index i
Subtracts LSB to move to next range
Collects disjoint ranges summing to prefix
Moves "left and down" in the tree

Update (point modification):

Starts at index i
Adds LSB to move to next covering index
Updates all ranges that contain position i
Moves "right and up" in the tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
For n = 16, comparing traversals:
 
QUERY(7) — Subtracts LSB          UPDATE(7) — Adds LSB
────────────────────              ─────────────────────
7 (0111) - 1 = 6                  7 (0111) + 1 = 8
6 (0110) - 2 = 4                  8 (1000) + 8 = 16
4 (0100) - 4 = 0                  16 > n, stop
 
Path: 7 → 6 → 4 → 0               Path: 7 → 8 → 16
Direction: Decreasing             Direction: Increasing
Role: Collect prefix sum          Role: Propagate update
 
QUERY(12) — Subtracts LSB         UPDATE(12) — Adds LSB
─────────────────────             ──────────────────────
12 (1100) - 4 = 8                 12 (1100) + 4 = 16
8 (1000) - 8 = 0                  16 > n, stop
 
Path: 12 → 8 → 0                  Path: 12 → 16
Direction: Decreasing             Direction: Increasing

Why this symmetry exists:

The LSB determines the "level" of each index in the implicit tree:

Larger LSB = higher level = covers more elements
Smaller LSB = lower level = covers fewer elements

Query needs to collect non-overlapping contributions, so it moves to smaller indices (lower or equal levels).

Update needs to reach all indices whose ranges include the updated position, which means climbing to higher levels.

Memory Aid

Think of it as: • Query descends: Going down to collect the pieces • Update ascends: Going up to notify all parents

Or: Query goes toward zero, Update goes toward n.

Why Updates Touch the Right Indices

Let's prove that the update algorithm correctly updates all—and only—the indices whose ranges include position i.

Claim:

For an update at position i, the algorithm visits exactly those indices j where:

j's range includes position i
i.e., j - LSB(j) + 1 ≤ i ≤ j

Proof Sketch:

Starting point: We begin at j = i. Since BIT[i] covers [i - LSB(i) + 1, i], and this range includes i, BIT[i] must be updated. ✓
Transition: From index j, we move to j' = j + LSB(j). We need to show j's range is contained in j''s range (or more specifically, position i is covered by j').
Key observation: Adding LSB(j) to j increases the index while ensuring the new range still includes position i, because j' ends at a higher position and its range extends back far enough to include i.
Termination: We stop when j > n, having visited all covering indices.

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
/**
 * Verify that update(i) touches exactly the correct indices.
 * 
 * An index j should be updated if and only if its range contains i.
 * Range of j: [j - LSB(j) + 1, j]
 */
function verifyUpdateIndices(i: number, n: number): void {
    // Find indices that SHOULD be updated (by checking ranges)
    const shouldUpdate: number[] = [];
    
    for (let j = 1; j <= n; j++) {
        const lsb = j & (-j);
        const rangeStart = j - lsb + 1;
        const rangeEnd = j;
        
        if (rangeStart <= i && i <= rangeEnd) {
            shouldUpdate.push(j);
        }
    }
    
    // Find indices that WOULD be updated by algorithm
    const wouldUpdate: number[] = [];
    let j = i;
    while (j <= n) {
        wouldUpdate.push(j);
        j += j & (-j);
    }
    
    // Compare
    console.log(`Position i = ${i}, n = ${n}`);
    console.log(`Should update: [${shouldUpdate.join(', ')}]`);
    console.log(`Would update:  [${wouldUpdate.join(', ')}]`);
    console.log(`Match: ${JSON.stringify(shouldUpdate) === JSON.stringify(wouldUpdate)}`);
    console.log();
}
 
// Test for various positions
verifyUpdateIndices(1, 16);
verifyUpdateIndices(5, 16);
verifyUpdateIndices(7, 16);
verifyUpdateIndices(12, 16);
 
/* Output:
Position i = 1, n = 16
Should update: [1, 2, 4, 8, 16]
Would update:  [1, 2, 4, 8, 16]
Match: true
 
Position i = 5, n = 16
Should update: [5, 6, 8, 16]
Would update:  [5, 6, 8, 16]
Match: true
 
Position i = 7, n = 16
Should update: [7, 8, 16]
Would update:  [7, 8, 16]
Match: true
 
Position i = 12, n = 16
Should update: [12, 16]
Would update:  [12, 16]
Match: true
*/

Initializing a BIT from an Array

To build a BIT from an initial array, we have several approaches:

Approach 1: Naive — O(n log n)

Call update(i, A[i]) for each element. Simple but not optimal.

Approach 2: Optimized — O(n)

Use the observation that each BIT[i] only needs to propagate to BIT[i + LSB(i)]. We can build bottom-up in linear time.

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
class FenwickTree {
    private tree: number[];
    private n: number;
 
    /**
     * Naive constructor: O(n log n)
     * Uses update() for each element.
     */
    static fromArrayNaive(arr: number[]): FenwickTree {
        const n = arr.length;
        const bit = new FenwickTree(n);
        
        // arr is 0-indexed, BIT is 1-indexed
        for (let i = 0; i < n; i++) {
            bit.update(i + 1, arr[i]);  // O(log n) per update
        }
        
        return bit;  // Total: O(n log n)
    }
 
    /**
     * Optimized constructor: O(n)
     * Each element propagates only to its immediate parent.
     */
    static fromArrayOptimized(arr: number[]): FenwickTree {
        const n = arr.length;
        const bit = new FenwickTree(n);
        
        // Start with the original values
        for (let i = 1; i <= n; i++) {
            bit.tree[i] = arr[i - 1];  // Copy original (0-indexed to 1-indexed)
        }
        
        // Propagate each value to its parent
        for (let i = 1; i <= n; i++) {
            const parent = i + (i & (-i));
            if (parent <= n) {
                bit.tree[parent] += bit.tree[i];
            }
        }
        
        return bit;  // Total: O(n)
    }
 
    /**
     * In-place construction from existing tree array.
     * Useful when you already have the tree allocated.
     */
    buildFromArray(arr: number[]): void {
        // Copy values
        for (let i = 1; i <= this.n; i++) {
            this.tree[i] = arr[i - 1];
        }
        
        // Propagate to parents
        for (let i = 1; i <= this.n; i++) {
            const parent = i + (i & (-i));
            if (parent <= this.n) {
                this.tree[parent] += this.tree[i];
            }
        }
    }
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    // ... update and query methods ...
}
 
// Verify both approaches produce identical results
const arr = [3, 1, 4, 1, 5, 9, 2, 6];
const bit1 = FenwickTree.fromArrayNaive(arr);
const bit2 = FenwickTree.fromArrayOptimized(arr);
 
// Both should give same query results
for (let i = 1; i <= arr.length; i++) {
    console.log(`prefix(${i}): naive=${bit1.query(i)}, opt=${bit2.query(i)}`);
}

When to Use Each Approach

Naive O(n log n): Fine for small arrays, simpler code, easier to understand Optimized O(n): Use for large arrays (millions of elements) or when initialization is frequent

In most applications, initialization happens once and queries/updates dominate, so the naive approach is often sufficient.

Set vs Add — Absolute Updates

The basic update operation adds a delta: A[i] += delta. But sometimes we need an absolute set: A[i] = newValue.

The Challenge:

A BIT doesn't store individual elements — it stores partial sums. To compute the required delta, we need to know the current value at position i.

Solution 1: Maintain separate array

Keep the original array alongside the BIT. For set(i, newValue):

Compute delta = newValue - originalArray[i]
Call update(i, delta)
Update originalArray[i] = newValue

Solution 2: Compute value from range query

A[i] = rangeQuery(i, i) = prefix(i) - prefix(i-1)

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
class FenwickTreeWithSet {
    private tree: number[];
    private values: number[];  // Original array for O(1) value lookup
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
        this.values = new Array(n + 1).fill(0);  // 1-indexed
    }
 
    /**
     * Add delta to position i.
     */
    add(i: number, delta: number): void {
        this.values[i] += delta;  // Track actual values
        
        while (i <= this.n) {
            this.tree[i] += delta;
            i += i & (-i);
        }
    }
 
    /**
     * Set position i to newValue (absolute update).
     */
    set(i: number, newValue: number): void {
        const delta = newValue - this.values[i];
        this.add(i, delta);
    }
 
    /**
     * Get the current value at position i.
     * O(1) with auxiliary array, or O(log n) from range query.
     */
    get(i: number): number {
        return this.values[i];
    }
 
    /**
     * Alternative: get value without auxiliary array.
     */
    getViaQuery(i: number): number {
        return this.query(i) - this.query(i - 1);
    }
 
    query(i: number): number {
        if (i <= 0) return 0;
        let sum = 0;
        while (i > 0) {
            sum += this.tree[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    rangeSum(l: number, r: number): number {
        return this.query(r) - this.query(l - 1);
    }
}
 
// Example usage
const bit = new FenwickTreeWithSet(10);
 
bit.set(3, 100);  // Set A[3] = 100
bit.set(5, 50);   // Set A[5] = 50
bit.add(3, 10);   // Add 10 to A[3], now A[3] = 110
 
console.log(bit.get(3));        // 110
console.log(bit.get(5));        // 50
console.log(bit.rangeSum(1, 5)); // 160 (0 + 0 + 110 + 0 + 50)
 
bit.set(3, 0);    // Reset A[3] to 0
console.log(bit.rangeSum(1, 5)); // 50

Space Trade-off

Maintaining the auxiliary values array doubles the space requirement. If you only need add operations (not set), you can omit it. If set operations are rare, consider computing values via range queries to save space.

Range Updates with Difference Arrays

A powerful technique combines BITs with difference arrays to support range updates — adding a value to all elements in a range [l, r].

The Insight:

Instead of storing A[i] in our BIT, we store the difference array D where:

D[1] = A[1]
D[i] = A[i] - A[i-1] for i > 1

A prefix sum of D gives us A[i]: A[i] = D[1] + D[2] + ... + D[i]

Range Update Property:

To add delta to all elements in [l, r]:

Add delta to D[l] (start of range)
Subtract delta from D[r+1] (end of range)

Only two point updates!

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
class RangeUpdateBIT {
    private diff: number[];  // Difference array stored in BIT
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.diff = new Array(n + 2).fill(0);  // +2 for r+1 boundary
    }
 
    /**
     * Internal: Update difference array at position i.
     */
    private updateDiff(i: number, delta: number): void {
        while (i <= this.n + 1) {
            this.diff[i] += delta;
            i += i & (-i);
        }
    }
 
    /**
     * Internal: Prefix sum of difference array = actual value at i.
     */
    private prefixDiff(i: number): number {
        let sum = 0;
        while (i > 0) {
            sum += this.diff[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    /**
     * Add delta to all elements in range [l, r].
     * 
     * Time Complexity: O(log n) — just two point updates!
     */
    rangeAdd(l: number, r: number, delta: number): void {
        this.updateDiff(l, delta);      // Start adding from l
        this.updateDiff(r + 1, -delta); // Stop adding after r
    }
 
    /**
     * Get the current value at position i.
     * 
     * Time Complexity: O(log n)
     */
    get(i: number): number {
        return this.prefixDiff(i);
    }
}
 
// Example: Range updates
const range = new RangeUpdateBIT(10);
 
range.rangeAdd(2, 5, 10);  // Add 10 to A[2..5]
range.rangeAdd(4, 8, 5);   // Add 5 to A[4..8]
 
// Check values
for (let i = 1; i <= 10; i++) {
    console.log(`A[${i}] = ${range.get(i)}`);
}
/* Output:
A[1] = 0
A[2] = 10
A[3] = 10
A[4] = 15  (10 + 5)
A[5] = 15  (10 + 5)
A[6] = 5
A[7] = 5
A[8] = 5
A[9] = 0
A[10] = 0
*/

For range updates AND range queries:

If you need both O(log n) range updates AND O(log n) range queries, you need two BITs with a more complex formula. This is sometimes called the "BIT of BIT" technique.

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
class RangeUpdateRangeQueryBIT {
    private bit1: number[];  // Stores diff[i]
    private bit2: number[];  // Stores i * diff[i]
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.bit1 = new Array(n + 2).fill(0);
        this.bit2 = new Array(n + 2).fill(0);
    }
 
    private updateBIT(bit: number[], i: number, delta: number): void {
        while (i <= this.n + 1) {
            bit[i] += delta;
            i += i & (-i);
        }
    }
 
    private queryBIT(bit: number[], i: number): number {
        let sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    /**
     * Add delta to all elements in range [l, r].
     * Time: O(log n)
     */
    rangeAdd(l: number, r: number, delta: number): void {
        // Update bit1 (difference array)
        this.updateBIT(this.bit1, l, delta);
        this.updateBIT(this.bit1, r + 1, -delta);
        
        // Update bit2 (for prefix sum formula)
        this.updateBIT(this.bit2, l, delta * (l - 1));
        this.updateBIT(this.bit2, r + 1, -delta * r);
    }
 
    /**
     * Get prefix sum from 1 to i.
     * Time: O(log n)
     */
    private prefixSum(i: number): number {
        // Formula: prefix(i) = bit1[i] * i - bit2[i]
        return this.queryBIT(this.bit1, i) * i - this.queryBIT(this.bit2, i);
    }
 
    /**
     * Get range sum from l to r.
     * Time: O(log n)
     */
    rangeSum(l: number, r: number): number {
        return this.prefixSum(r) - this.prefixSum(l - 1);
    }
}
 
// Example with both range updates and range queries
const full = new RangeUpdateRangeQueryBIT(10);
 
full.rangeAdd(1, 5, 10);   // Add 10 to A[1..5]
full.rangeAdd(3, 7, 5);    // Add 5 to A[3..7]
 
console.log(full.rangeSum(1, 10));  // Total sum
console.log(full.rangeSum(3, 5));   // Sum of [3..5] = 15 + 15 + 15 = 45

Edge Cases and Error Handling

Production-quality update operations must handle edge cases gracefully:

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
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);
    }
 
    /**
     * Robust update with full validation.
     */
    update(i: number, delta: number): void {
        // Edge case 1: Index out of bounds
        if (i < 1) {
            throw new Error(`Index ${i} is below minimum (1)`);
        }
        if (i > this.n) {
            throw new Error(`Index ${i} exceeds maximum (${this.n})`);
        }
 
        // Edge case 2: Delta is zero (no-op optimization)
        if (delta === 0) {
            return;
        }
 
        // Edge case 3: Handle potential overflow (in real production)
        // In JS, numbers are 64-bit floats, but for integer overflow:
        // if (Math.abs(this.tree[i] + delta) > Number.MAX_SAFE_INTEGER) {
        //     throw new Error("Integer overflow detected");
        // }
 
        // Normal update
        while (i <= this.n) {
            this.tree[i] += delta;
            i += i & (-i);
        }
    }
 
    /**
     * Safe update that silently ignores invalid indices.
     * Useful in signal processing or when validation is done elsewhere.
     */
    updateSafe(i: number, delta: number): boolean {
        if (i < 1 || i > this.n || delta === 0) {
            return false;  // Indicate update was skipped
        }
 
        while (i <= this.n) {
            this.tree[i] += delta;
            i += i & (-i);
        }
        
        return true;
    }
 
    /**
     * Batch update — more efficient than individual updates when
     * updating many positions.
     */
    batchUpdate(updates: Array<{ index: number; delta: number }>): number {
        let successCount = 0;
        
        for (const { index, delta } of updates) {
            if (this.updateSafe(index, delta)) {
                successCount++;
            }
        }
        
        return successCount;
    }
}
 
// Edge case testing
const bit = new RobustFenwickTree(10);
 
// Zero delta — no-op
bit.update(5, 0);  // Returns immediately
 
// Boundary values
bit.update(1, 100);   // Minimum index — OK
bit.update(10, 50);   // Maximum index — OK
 
// Invalid indices
try {
    bit.update(0, 10);   // Below range
} catch (e) {
    console.log("Caught:", e.message);
}
 
try {
    bit.update(11, 10);  // Above range
} catch (e) {
    console.log("Caught:", e.message);
}
 
// Safe update for invalid index
console.log(bit.updateSafe(-5, 100));  // false, no error

Update Edge Cases Summary
Edge Case	Input	Recommended Behavior
Zero delta	update(i, 0)	Return early (no-op)
Index = 0	update(0, delta)	Throw or return false
Index < 0	update(-5, delta)	Throw or return false
Index > n	update(n+1, delta)	Throw or return false
Index = 1 (min)	update(1, delta)	Valid, update normally
Index = n (max)	update(n, delta)	Valid, update normally

Summary — Mastering BIT Updates

This page provided comprehensive coverage of point update operations in Fenwick Trees. Here are the key takeaways:

Key Takeaways

•Update algorithm adds the lowest set bit repeatedly (i += i & -i) to propagate changes upward.
•Symmetry: Queries subtract LSB (descend), updates add LSB (ascend) — complementary traversals.
•Update touches O(log n) indices — exactly those whose ranges include the updated position.
•O(n) initialization is possible by propagating each value only to its immediate parent.
•Set operations require knowing the current value — maintain an auxiliary array or compute via range query.
•Range updates are possible with difference arrays: update(l) and update(r+1) only.
•Two BITs support both O(log n) range updates AND O(log n) range queries.

What's next:

With both queries and updates mastered, the final page analyzes the complete time and space complexity of Fenwick Trees, comparing them to alternatives and providing a comprehensive decision framework for when to use BITs.

Page Complete

You now have complete mastery of BIT updates — from basic point updates to advanced range update techniques. You understand the symmetry between queries and updates, can initialize BITs efficiently, and can implement robust update operations for production use.

4 / 5

Loading learning content...

Data Structures & AlgorithmsFenwick Trees (Binary Indexed Trees)

Fenwick Trees — Binary Indexed Trees

LevelAdvanced

Duration90 mins

TopicFenwick Trees (Binary Indexed Trees)

4 / 5

Point Updates

Dynamic Data — The Power of Updates

A prefix sum array could answer range queries in O(1) time — far better than BIT's O(log n). So why use a Fenwick Tree?

This page examines point updates in complete detail: the algorithm, its mechanics, the relationship between updates and queries, and advanced patterns for handling range updates.

What You Will Learn

The Update Algorithm — Step by Step

The update operation adds a value (delta) to an element at a given index. After the update, all future queries must reflect this change.

The Update Goal:

Given an index i and a value delta, perform:

A[i] = A[i] + delta

And update the BIT so all future prefix queries are correct.

The Algorithm:

function update(i, delta):
    while i <= n:
        BIT[i] = BIT[i] + delta
        i = i + (i & -i)    // Add lowest set bit

Why it works:

Every BIT index j whose range includes position i must be updated. The algorithm finds these indices by starting at i and repeatedly adding the LSB, which moves to the next "covering" index.

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
class FenwickTree {
    private tree: number[];
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    /**
     * Add delta to the element at index i.
     * 
     * @param i - The index to update (1-indexed)
     * @param delta - The value to add (can be negative)
     * 
     * Preconditions:
     *   - 1 <= i <= n
     * 
     * Postconditions:
     *   - All BIT entries covering index i are updated
     *   - Future queries will reflect the change
     * 
     * Time Complexity: O(log n)
     */
    update(i: number, delta: number): void {
        // Validate input
        if (i < 1 || i > this.n) {
            throw new Error(`Index ${i} out of bounds [1, ${this.n}]`);
        }
        
        // Propagate update to all covering indices
        while (i <= this.n) {
            this.tree[i] += delta;
            i += i & (-i);  // Add lowest set bit
        }
    }
 
    /**
     * Update with detailed tracing for educational purposes.
     */
    updateWithTrace(i: number, delta: number): number[] {
        const trace: number[] = [];
        
        while (i <= this.n) {
            trace.push(i);
            this.tree[i] += delta;
            i += i & (-i);
        }
        
        return trace;
    }
}
 
// Example with tracing
const bit = new FenwickTree(16);
 
// Update position 3 with delta = 5
const trace = bit.updateWithTrace(3, 5);
console.log("Indices updated:", trace);
// Output: [3, 4, 8, 16]
// 3 (0011) → +1 → 4 (0100) → +4 → 8 (1000) → +8 → 16 (10000) → done
 
// Update position 7 with delta = 10
const trace2 = bit.updateWithTrace(7, 10);
console.log("Indices updated:", trace2);
// Output: [7, 8, 16]

Add vs Subtract LSB

Query subtracts the LSB: i -= i & (-i) — moves to previous disjoint range Update adds the LSB: i += i & (-i) — moves to next covering index

These are complementary operations that traverse the implicit tree in opposite directions.

Complete Trace Examples

Let's trace the update algorithm for several inputs to build deep intuition about propagation:

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
Update(1, 5):
 
i = 1 (binary: 0001)
├── LSB(1) = 1
├── BIT[1] covers [1..1] — includes position 1 ✓
├── BIT[1] += 5
└── Next: i = 1 + 1 = 2
 
i = 2 (binary: 0010)
├── LSB(2) = 2
├── BIT[2] covers [1..2] — includes position 1 ✓
├── BIT[2] += 5
└── Next: i = 2 + 2 = 4
 
i = 4 (binary: 0100)
├── LSB(4) = 4
├── BIT[4] covers [1..4] — includes position 1 ✓
├── BIT[4] += 5
└── Next: i = 4 + 4 = 8
 
i = 8 (binary: 1000)
├── LSB(8) = 8
├── BIT[8] covers [1..8] — includes position 1 ✓
├── BIT[8] += 5
└── Next: i = 8 + 8 = 16
 
i = 16 (binary: 10000)
├── LSB(16) = 16
├── BIT[16] covers [1..16] — includes position 1 ✓
├── BIT[16] += 5
└── Next: i = 16 + 16 = 32 > n, STOP
 
Indices updated: [1, 2, 4, 8, 16]
All ranges covering position 1 were updated correctly!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Update(5, 7):
 
i = 5 (binary: 0101)
├── LSB(5) = 1
├── BIT[5] covers [5..5] — includes position 5 ✓
├── BIT[5] += 7
└── Next: i = 5 + 1 = 6
 
i = 6 (binary: 0110)
├── LSB(6) = 2
├── BIT[6] covers [5..6] — includes position 5 ✓
├── BIT[6] += 7
└── Next: i = 6 + 2 = 8
 
i = 8 (binary: 1000)
├── LSB(8) = 8
├── BIT[8] covers [1..8] — includes position 5 ✓
├── BIT[8] += 7
└── Next: i = 8 + 8 = 16
 
i = 16 (beyond n=8 in this example), STOP
 
Indices updated: [5, 6, 8]
Exactly the indices whose ranges include position 5!

Update Propagation Paths (for n = 16)
Position i	Binary	Indices Updated	Count
1	00001	1, 2, 4, 8, 16	5
3	00011	3, 4, 8, 16	4
4	00100	4, 8, 16	3
5	00101	5, 6, 8, 16	4
7	00111	7, 8, 16	3
8	01000	8, 16	2
10	01010	10, 12, 16	3
12	01100	12, 16	2
15	01111	15, 16	2
16	10000	16	1

Iteration Count Pattern

The Symmetry Between Updates and Queries

There's a beautiful symmetry in how queries and updates traverse the BIT:

Query (prefix sum):

Starts at index i
Subtracts LSB to move to next range
Collects disjoint ranges summing to prefix
Moves "left and down" in the tree

Update (point modification):

Starts at index i
Adds LSB to move to next covering index
Updates all ranges that contain position i
Moves "right and up" in the tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
For n = 16, comparing traversals:
 
QUERY(7) — Subtracts LSB          UPDATE(7) — Adds LSB
────────────────────              ─────────────────────
7 (0111) - 1 = 6                  7 (0111) + 1 = 8
6 (0110) - 2 = 4                  8 (1000) + 8 = 16
4 (0100) - 4 = 0                  16 > n, stop
 
Path: 7 → 6 → 4 → 0               Path: 7 → 8 → 16
Direction: Decreasing             Direction: Increasing
Role: Collect prefix sum          Role: Propagate update
 
QUERY(12) — Subtracts LSB         UPDATE(12) — Adds LSB
─────────────────────             ──────────────────────
12 (1100) - 4 = 8                 12 (1100) + 4 = 16
8 (1000) - 8 = 0                  16 > n, stop
 
Path: 12 → 8 → 0                  Path: 12 → 16
Direction: Decreasing             Direction: Increasing

Why this symmetry exists:

The LSB determines the "level" of each index in the implicit tree:

Larger LSB = higher level = covers more elements
Smaller LSB = lower level = covers fewer elements

Query needs to collect non-overlapping contributions, so it moves to smaller indices (lower or equal levels).

Update needs to reach all indices whose ranges include the updated position, which means climbing to higher levels.

Memory Aid

Think of it as: • Query descends: Going down to collect the pieces • Update ascends: Going up to notify all parents

Or: Query goes toward zero, Update goes toward n.

Why Updates Touch the Right Indices

Let's prove that the update algorithm correctly updates all—and only—the indices whose ranges include position i.

Claim:

For an update at position i, the algorithm visits exactly those indices j where:

j's range includes position i
i.e., j - LSB(j) + 1 ≤ i ≤ j

Proof Sketch:

Starting point: We begin at j = i. Since BIT[i] covers [i - LSB(i) + 1, i], and this range includes i, BIT[i] must be updated. ✓
Transition: From index j, we move to j' = j + LSB(j). We need to show j's range is contained in j''s range (or more specifically, position i is covered by j').
Key observation: Adding LSB(j) to j increases the index while ensuring the new range still includes position i, because j' ends at a higher position and its range extends back far enough to include i.
Termination: We stop when j > n, having visited all covering indices.

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
/**
 * Verify that update(i) touches exactly the correct indices.
 * 
 * An index j should be updated if and only if its range contains i.
 * Range of j: [j - LSB(j) + 1, j]
 */
function verifyUpdateIndices(i: number, n: number): void {
    // Find indices that SHOULD be updated (by checking ranges)
    const shouldUpdate: number[] = [];
    
    for (let j = 1; j <= n; j++) {
        const lsb = j & (-j);
        const rangeStart = j - lsb + 1;
        const rangeEnd = j;
        
        if (rangeStart <= i && i <= rangeEnd) {
            shouldUpdate.push(j);
        }
    }
    
    // Find indices that WOULD be updated by algorithm
    const wouldUpdate: number[] = [];
    let j = i;
    while (j <= n) {
        wouldUpdate.push(j);
        j += j & (-j);
    }
    
    // Compare
    console.log(`Position i = ${i}, n = ${n}`);
    console.log(`Should update: [${shouldUpdate.join(', ')}]`);
    console.log(`Would update:  [${wouldUpdate.join(', ')}]`);
    console.log(`Match: ${JSON.stringify(shouldUpdate) === JSON.stringify(wouldUpdate)}`);
    console.log();
}
 
// Test for various positions
verifyUpdateIndices(1, 16);
verifyUpdateIndices(5, 16);
verifyUpdateIndices(7, 16);
verifyUpdateIndices(12, 16);
 
/* Output:
Position i = 1, n = 16
Should update: [1, 2, 4, 8, 16]
Would update:  [1, 2, 4, 8, 16]
Match: true
 
Position i = 5, n = 16
Should update: [5, 6, 8, 16]
Would update:  [5, 6, 8, 16]
Match: true
 
Position i = 7, n = 16
Should update: [7, 8, 16]
Would update:  [7, 8, 16]
Match: true
 
Position i = 12, n = 16
Should update: [12, 16]
Would update:  [12, 16]
Match: true
*/

Initializing a BIT from an Array

To build a BIT from an initial array, we have several approaches:

Approach 1: Naive — O(n log n)

Call update(i, A[i]) for each element. Simple but not optimal.

Approach 2: Optimized — O(n)

Use the observation that each BIT[i] only needs to propagate to BIT[i + LSB(i)]. We can build bottom-up in linear time.

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
class FenwickTree {
    private tree: number[];
    private n: number;
 
    /**
     * Naive constructor: O(n log n)
     * Uses update() for each element.
     */
    static fromArrayNaive(arr: number[]): FenwickTree {
        const n = arr.length;
        const bit = new FenwickTree(n);
        
        // arr is 0-indexed, BIT is 1-indexed
        for (let i = 0; i < n; i++) {
            bit.update(i + 1, arr[i]);  // O(log n) per update
        }
        
        return bit;  // Total: O(n log n)
    }
 
    /**
     * Optimized constructor: O(n)
     * Each element propagates only to its immediate parent.
     */
    static fromArrayOptimized(arr: number[]): FenwickTree {
        const n = arr.length;
        const bit = new FenwickTree(n);
        
        // Start with the original values
        for (let i = 1; i <= n; i++) {
            bit.tree[i] = arr[i - 1];  // Copy original (0-indexed to 1-indexed)
        }
        
        // Propagate each value to its parent
        for (let i = 1; i <= n; i++) {
            const parent = i + (i & (-i));
            if (parent <= n) {
                bit.tree[parent] += bit.tree[i];
            }
        }
        
        return bit;  // Total: O(n)
    }
 
    /**
     * In-place construction from existing tree array.
     * Useful when you already have the tree allocated.
     */
    buildFromArray(arr: number[]): void {
        // Copy values
        for (let i = 1; i <= this.n; i++) {
            this.tree[i] = arr[i - 1];
        }
        
        // Propagate to parents
        for (let i = 1; i <= this.n; i++) {
            const parent = i + (i & (-i));
            if (parent <= this.n) {
                this.tree[parent] += this.tree[i];
            }
        }
    }
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }
 
    // ... update and query methods ...
}
 
// Verify both approaches produce identical results
const arr = [3, 1, 4, 1, 5, 9, 2, 6];
const bit1 = FenwickTree.fromArrayNaive(arr);
const bit2 = FenwickTree.fromArrayOptimized(arr);
 
// Both should give same query results
for (let i = 1; i <= arr.length; i++) {
    console.log(`prefix(${i}): naive=${bit1.query(i)}, opt=${bit2.query(i)}`);
}

When to Use Each Approach

Naive O(n log n): Fine for small arrays, simpler code, easier to understand Optimized O(n): Use for large arrays (millions of elements) or when initialization is frequent

In most applications, initialization happens once and queries/updates dominate, so the naive approach is often sufficient.

Set vs Add — Absolute Updates

The basic update operation adds a delta: A[i] += delta. But sometimes we need an absolute set: A[i] = newValue.

The Challenge:

A BIT doesn't store individual elements — it stores partial sums. To compute the required delta, we need to know the current value at position i.

Solution 1: Maintain separate array

Keep the original array alongside the BIT. For set(i, newValue):

Compute delta = newValue - originalArray[i]
Call update(i, delta)
Update originalArray[i] = newValue

Solution 2: Compute value from range query

A[i] = rangeQuery(i, i) = prefix(i) - prefix(i-1)

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
class FenwickTreeWithSet {
    private tree: number[];
    private values: number[];  // Original array for O(1) value lookup
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
        this.values = new Array(n + 1).fill(0);  // 1-indexed
    }
 
    /**
     * Add delta to position i.
     */
    add(i: number, delta: number): void {
        this.values[i] += delta;  // Track actual values
        
        while (i <= this.n) {
            this.tree[i] += delta;
            i += i & (-i);
        }
    }
 
    /**
     * Set position i to newValue (absolute update).
     */
    set(i: number, newValue: number): void {
        const delta = newValue - this.values[i];
        this.add(i, delta);
    }
 
    /**
     * Get the current value at position i.
     * O(1) with auxiliary array, or O(log n) from range query.
     */
    get(i: number): number {
        return this.values[i];
    }
 
    /**
     * Alternative: get value without auxiliary array.
     */
    getViaQuery(i: number): number {
        return this.query(i) - this.query(i - 1);
    }
 
    query(i: number): number {
        if (i <= 0) return 0;
        let sum = 0;
        while (i > 0) {
            sum += this.tree[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    rangeSum(l: number, r: number): number {
        return this.query(r) - this.query(l - 1);
    }
}
 
// Example usage
const bit = new FenwickTreeWithSet(10);
 
bit.set(3, 100);  // Set A[3] = 100
bit.set(5, 50);   // Set A[5] = 50
bit.add(3, 10);   // Add 10 to A[3], now A[3] = 110
 
console.log(bit.get(3));        // 110
console.log(bit.get(5));        // 50
console.log(bit.rangeSum(1, 5)); // 160 (0 + 0 + 110 + 0 + 50)
 
bit.set(3, 0);    // Reset A[3] to 0
console.log(bit.rangeSum(1, 5)); // 50

Space Trade-off

Range Updates with Difference Arrays

A powerful technique combines BITs with difference arrays to support range updates — adding a value to all elements in a range [l, r].

The Insight:

Instead of storing A[i] in our BIT, we store the difference array D where:

D[1] = A[1]
D[i] = A[i] - A[i-1] for i > 1

A prefix sum of D gives us A[i]: A[i] = D[1] + D[2] + ... + D[i]

Range Update Property:

To add delta to all elements in [l, r]:

Add delta to D[l] (start of range)
Subtract delta from D[r+1] (end of range)

Only two point updates!

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
class RangeUpdateBIT {
    private diff: number[];  // Difference array stored in BIT
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.diff = new Array(n + 2).fill(0);  // +2 for r+1 boundary
    }
 
    /**
     * Internal: Update difference array at position i.
     */
    private updateDiff(i: number, delta: number): void {
        while (i <= this.n + 1) {
            this.diff[i] += delta;
            i += i & (-i);
        }
    }
 
    /**
     * Internal: Prefix sum of difference array = actual value at i.
     */
    private prefixDiff(i: number): number {
        let sum = 0;
        while (i > 0) {
            sum += this.diff[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    /**
     * Add delta to all elements in range [l, r].
     * 
     * Time Complexity: O(log n) — just two point updates!
     */
    rangeAdd(l: number, r: number, delta: number): void {
        this.updateDiff(l, delta);      // Start adding from l
        this.updateDiff(r + 1, -delta); // Stop adding after r
    }
 
    /**
     * Get the current value at position i.
     * 
     * Time Complexity: O(log n)
     */
    get(i: number): number {
        return this.prefixDiff(i);
    }
}
 
// Example: Range updates
const range = new RangeUpdateBIT(10);
 
range.rangeAdd(2, 5, 10);  // Add 10 to A[2..5]
range.rangeAdd(4, 8, 5);   // Add 5 to A[4..8]
 
// Check values
for (let i = 1; i <= 10; i++) {
    console.log(`A[${i}] = ${range.get(i)}`);
}
/* Output:
A[1] = 0
A[2] = 10
A[3] = 10
A[4] = 15  (10 + 5)
A[5] = 15  (10 + 5)
A[6] = 5
A[7] = 5
A[8] = 5
A[9] = 0
A[10] = 0
*/

For range updates AND range queries:

If you need both O(log n) range updates AND O(log n) range queries, you need two BITs with a more complex formula. This is sometimes called the "BIT of BIT" technique.

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
class RangeUpdateRangeQueryBIT {
    private bit1: number[];  // Stores diff[i]
    private bit2: number[];  // Stores i * diff[i]
    private n: number;
 
    constructor(n: number) {
        this.n = n;
        this.bit1 = new Array(n + 2).fill(0);
        this.bit2 = new Array(n + 2).fill(0);
    }
 
    private updateBIT(bit: number[], i: number, delta: number): void {
        while (i <= this.n + 1) {
            bit[i] += delta;
            i += i & (-i);
        }
    }
 
    private queryBIT(bit: number[], i: number): number {
        let sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= i & (-i);
        }
        return sum;
    }
 
    /**
     * Add delta to all elements in range [l, r].
     * Time: O(log n)
     */
    rangeAdd(l: number, r: number, delta: number): void {
        // Update bit1 (difference array)
        this.updateBIT(this.bit1, l, delta);
        this.updateBIT(this.bit1, r + 1, -delta);
        
        // Update bit2 (for prefix sum formula)
        this.updateBIT(this.bit2, l, delta * (l - 1));
        this.updateBIT(this.bit2, r + 1, -delta * r);
    }
 
    /**
     * Get prefix sum from 1 to i.
     * Time: O(log n)
     */
    private prefixSum(i: number): number {
        // Formula: prefix(i) = bit1[i] * i - bit2[i]
        return this.queryBIT(this.bit1, i) * i - this.queryBIT(this.bit2, i);
    }
 
    /**
     * Get range sum from l to r.
     * Time: O(log n)
     */
    rangeSum(l: number, r: number): number {
        return this.prefixSum(r) - this.prefixSum(l - 1);
    }
}
 
// Example with both range updates and range queries
const full = new RangeUpdateRangeQueryBIT(10);
 
full.rangeAdd(1, 5, 10);   // Add 10 to A[1..5]
full.rangeAdd(3, 7, 5);    // Add 5 to A[3..7]
 
console.log(full.rangeSum(1, 10));  // Total sum
console.log(full.rangeSum(3, 5));   // Sum of [3..5] = 15 + 15 + 15 = 45

Edge Cases and Error Handling

Production-quality update operations must handle edge cases gracefully:

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
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);
    }
 
    /**
     * Robust update with full validation.
     */
    update(i: number, delta: number): void {
        // Edge case 1: Index out of bounds
        if (i < 1) {
            throw new Error(`Index ${i} is below minimum (1)`);
        }
        if (i > this.n) {
            throw new Error(`Index ${i} exceeds maximum (${this.n})`);
        }
 
        // Edge case 2: Delta is zero (no-op optimization)
        if (delta === 0) {
            return;
        }
 
        // Edge case 3: Handle potential overflow (in real production)
        // In JS, numbers are 64-bit floats, but for integer overflow:
        // if (Math.abs(this.tree[i] + delta) > Number.MAX_SAFE_INTEGER) {
        //     throw new Error("Integer overflow detected");
        // }
 
        // Normal update
        while (i <= this.n) {
            this.tree[i] += delta;
            i += i & (-i);
        }
    }
 
    /**
     * Safe update that silently ignores invalid indices.
     * Useful in signal processing or when validation is done elsewhere.
     */
    updateSafe(i: number, delta: number): boolean {
        if (i < 1 || i > this.n || delta === 0) {
            return false;  // Indicate update was skipped
        }
 
        while (i <= this.n) {
            this.tree[i] += delta;
            i += i & (-i);
        }
        
        return true;
    }
 
    /**
     * Batch update — more efficient than individual updates when
     * updating many positions.
     */
    batchUpdate(updates: Array<{ index: number; delta: number }>): number {
        let successCount = 0;
        
        for (const { index, delta } of updates) {
            if (this.updateSafe(index, delta)) {
                successCount++;
            }
        }
        
        return successCount;
    }
}
 
// Edge case testing
const bit = new RobustFenwickTree(10);
 
// Zero delta — no-op
bit.update(5, 0);  // Returns immediately
 
// Boundary values
bit.update(1, 100);   // Minimum index — OK
bit.update(10, 50);   // Maximum index — OK
 
// Invalid indices
try {
    bit.update(0, 10);   // Below range
} catch (e) {
    console.log("Caught:", e.message);
}
 
try {
    bit.update(11, 10);  // Above range
} catch (e) {
    console.log("Caught:", e.message);
}
 
// Safe update for invalid index
console.log(bit.updateSafe(-5, 100));  // false, no error

Update Edge Cases Summary
Edge Case	Input	Recommended Behavior
Zero delta	update(i, 0)	Return early (no-op)
Index = 0	update(0, delta)	Throw or return false
Index < 0	update(-5, delta)	Throw or return false
Index > n	update(n+1, delta)	Throw or return false
Index = 1 (min)	update(1, delta)	Valid, update normally
Index = n (max)	update(n, delta)	Valid, update normally

Summary — Mastering BIT Updates

This page provided comprehensive coverage of point update operations in Fenwick Trees. Here are the key takeaways:

Key Takeaways

•Update algorithm adds the lowest set bit repeatedly (i += i & -i) to propagate changes upward.
•Symmetry: Queries subtract LSB (descend), updates add LSB (ascend) — complementary traversals.
•Update touches O(log n) indices — exactly those whose ranges include the updated position.
•O(n) initialization is possible by propagating each value only to its immediate parent.
•Set operations require knowing the current value — maintain an auxiliary array or compute via range query.
•Range updates are possible with difference arrays: update(l) and update(r+1) only.
•Two BITs support both O(log n) range updates AND O(log n) range queries.

What's next:

Page Complete

4 / 5