# Binary Indexed Tree (BIT)
##### Aji Hsu 2025/04/15
---

## Usage

To efficiently update and query prefix sums dynamically.

### Compare to Traditional Prefix Sum
* Traditional
* update: `TC = O(N)`
* get: `TC = O(1)`
* Binary Indexed Tree
* update: `TC = O(log(N)))`
* get: `TC = O(log(N))`

### Example
Given
`nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };`
`prefixSum = { 1, 3, 6, 10, 15, 21, 28, 36, 45 };`

* Traditional prefix sum
* If we want to add 1 to the `nums[0]`, it costs `TC = O(N)` to update the `prefixSum`.

prefixSum = { 2, 4, 7, 11, 16, 22, 29, 37, 46 };

* Binary Indexed Tree
* Update the `prefixSum` with `TC = O(log(N))`

---

## Implement Binary Indexed Tree

### Concept
**Traditional:**
`nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };`
`prefixSum = { 1, 3, 6, 10, 15, 21, 28, 36, 45 };`

**BIT(1-indexed):**
`nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };`
`prefixSum = { 1, 3, 3, 10, 5, 11, 7, 36, 9 };`
where:
* index-1 store `nums[1]`
* index-2 store `nums[1]~nums[2]`
* index-3 store `nums[3]`
* index-4 store `nums[1]~nums[4]`
* index-5 store `nums[5]`
* index-6 store `nums[5]~nums[6]`
* index-7 store `nums[7]`
* index-8 store `nums[1]~nums[8]`
* index-9 store `nums[9]`

We can compute prefix sums by:
* `sum[1] = prefixSum[1]`
* `sum[2] = prefixSum[2]`
* `sum[3] = prefixSum[3] + prefixSum[2]`
* `sum[4] = prefixSum[4]`
* `sum[5] = prefixSum[4] + prefixSum[5]`
* `sum[6] = prefixSum[6] + prefixSum[4]`
* `sum[7] = prefixSum[7] + prefixSum[6] + prefixSum[4]`
* `sum[8] = prefixSum[8]`
* `sum[9] = prefixSum[9] + prefixSum[8]`

We can update prefix sums by:
* `nums[1] += d --> prefixSum[1], prefixSum[2], prefixSum[8] += d`
* `nums[2] += d --> prefixSum[2], prefixSum[4], prefixSum[8] += d`
* `nums[3] += d --> prefixSum[3], prefixSum[4], prefixSum[8] += d`
* `nums[4] += d --> prefixSum[4], prefixSum[8] += d`
* `nums[5] += d --> prefixSum[5], prefixSum[6], prefixSum[8] += d`
* `nums[6] += d --> prefixSum[6], prefixSum[8] += d`
* `nums[7] += d --> prefixSum[7], prefixSum[8] += d`
* `nums[8] += d --> prefixSum[8] += d`
* `nums[9] += d --> prefixSum[9] += d`

==**Thus, what we should do is to find a even way to split sum into segments optimally.**==

### Lowbit

* lowbit: the rightmost 1-bit in binary

lowbit = n & -n;

* example
* $(6)_{10} = (0110)_2$ -->lowbit=$(0010)_2 = (2)_{10}$
* $(8)_{10} = (1000)_2$ -->lowbit=$(1000)_2 = (8)_{10}$

**We use lowbit to define the interval that prefixSum[i] represents.**

* example
* lowbit(6)=2 -->`prefixSum[6]` store the number of interval `(6-2, 6]` that is `[5, 6]`
* lowbit(8)=8 -->`prefixSum[6]` store the number of interval `(8-8, 8]` that is `[1, 8]`

**Explanation of the way we get sum**

Given

i
j = i - lowbit(i)
k = j - lowbit(j)
l = k - lowbit(k)
.
.
.

We can conclude that:
`sum[i] = prefixSum[i] + prefixSum[j] + prefixSum[k] ...`

* example
* `sum[6] = prefixSum[6] + prefixSum[4]` means -->
* `sum[6] = prefixSum[6] + prefixSum[6 - Lowbit(6)]`

**Explanation of the way we update sum**

* example
* `nums[6] += d --> prefixSum[6], prefixSum[8] += d` means -->
* `nums[6] += d --> prefixSum[6], prefixSum[6 + lowbit(6)] += d`

**Reason we choose lowbit to implement**

Given i = $(100101)_{2}$

**Get sum:**
Minus lowbit until `i == 0`
$(100101)_{2} \rightarrow (100100)_{2} \rightarrow (100000)_{2} \rightarrow (000000)_{2}$

We can know the total `TC = O(digit) = O(log(N))`

**Update sum:**
If array size = $(111111)_{2}$
Add lowbit until `i >= n`
$(100101)_{2} \rightarrow (100110)_{2} \rightarrow (101000)_{2} \rightarrow (110000)_{2} \rightarrow (1100000)_{2}$

We can know the total `TC = O(digit) = O(log(N))`

### Implement (Java)

* `query()`: get sum
* `update()`: update

class BIT {
    private int[] arr;

    BIT(int n) {
        arr = new int[n + 1];
    }

    public void update(int i, int delta) {
        i++;
        while (i < arr.length) {
            arr[i] += delta;
            i += i & -i;
        }
    }

    public int query(int i) {
        i++;
        int total = 0;
        while (i > 0) {
            total += arr[i];
            i -= i & -i;
        }
        return total;
    }
}