Binary Indexed Tree (Fenwick Tree)

class BinaryIndexedTree {
    constructor(arr) {
        this.n = arr.length;
        this.BITree = new Array(this.n + 1).fill(0);
 
        // Construct the BITree by inserting values one by one
        for (let i = 0; i < this.n; i++) {
            this.update(i, arr[i]);
        }
    }
 
    // Update the BIT at a specific index by a given value
    update(index, val) {
        // Transform to 1-based indexing for the BITree
        let i = index + 1;
 
        // Traverse all ancestors and add val
        while (i <= this.n) {
            this.BITree[i] += val;
 
            // Move index to parent/next node
            i += i & -i;
        }
    }
 
    // Helper to get prefix sum of arr[0..index]
    getSum(index) {
        let sum = 0;
        let i = index + 1; // 1-based indexing
 
        // Traverse ancestors of index
        while (i > 0) {
            sum += this.BITree[i];
 
            // Move index to parent node (clear the last set bit)
            i -= i & -i;
        }
        return sum;
    }
 
    // Get range sum in [L, R]
    getRangeSum(L, R) {
        if (L === 0) return this.getSum(R);
        return this.getSum(R) - this.getSum(L - 1);
    }
}
 
// Driver Code
const arr = [2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9];
const bit = new BinaryIndexedTree(arr);
 
// Get sum of first 5 elements (indices 0 to 4: 2 + 1 + 1 + 3 + 2 = 9)
console.log("Sum of elements in arr[0..4]:", bit.getSum(4));
 
// Update index 3 by adding 6 (arr[3] becomes 3 + 6 = 9)
bit.update(3, 6);
 
// Get sum of first 5 elements again (2 + 1 + 1 + 9 + 2 = 15)
console.log("Sum in arr[0..4] after update:", bit.getSum(4));