Fenwick Tree (BIT)

// 1D Fenwick Tree (1-indexed)
class BIT {
    constructor(n) { this.n = n; this.tree = new Array(n + 1).fill(0); }
    update(i, delta) {
        for (; i <= this.n; i += i & (-i)) this.tree[i] += delta;
    }
    query(i) { // prefix sum [1..i]
        let s = 0;
        for (; i > 0; i -= i & (-i)) s += this.tree[i];
        return s;
    }
    rangeQuery(l, r) { return this.query(r) - this.query(l - 1); }
    // Point query (when using BIT as difference array):
    // update(l, +1), update(r+1, -1) → query(i) gives range add value at i
}

// 2D Fenwick Tree
class BIT2D {
    constructor(m, n) { this.m = m; this.n = n; this.t = Array.from({length:m+1},()=>new Array(n+1).fill(0)); }
    update(r, c, v) {
        for (let i = r; i <= this.m; i += i & (-i))
            for (let j = c; j <= this.n; j += j & (-j))
                this.t[i][j] += v;
    }
    query(r, c) {
        let s = 0;
        for (let i = r; i > 0; i -= i & (-i))
            for (let j = c; j > 0; j -= j & (-j))
                s += this.t[i][j];
        return s;
    }
    rangeQuery(r1, c1, r2, c2) {
        return this.query(r2,c2) - this.query(r1-1,c2) - this.query(r2,c1-1) + this.query(r1-1,c1-1);
    }
}