# Fenwick Tree

## Range Sum Query

Given an array `A` of size `n`, and `m` queries, where each query asks the sum of a range in `A`.

For example, `A = [1, 2, 4, 2, 3, 4]`, and `query = [[1, 2], [1, 4]]`. The answer to the `query[0]` is `2+4=6`, and `2+4+2+3=11` for `query[1]`.

The naive way to do this is to sum over the range for each query, and this give `O(mn)` time complexity.

### Prefix Sum

A better way to do this is by precomputing the **prefix sum**. We will make another array `P`, where `P[i]=A[0]+A[1]+...+A[i]`. Moreover, `P[i] = P[i-1]+A[i]`, for `i=1 to n-1`. So we can compute `P` in `O(n)` time.

Also, each query `q` can be computed by `P[q[1]] - P[q[0]-1]`, so it takes `O(n + m)` time to solve the probelm.

**Follow up**
What if we want to modify `A` during the queries? If we modify at `A[i]`, then we need to update `P[i]` to `P[n-1]`, which runs in `O(n)` time.

So we can see that prefix sum takes `O(1)` time for RSQ and `O(n)` time for update.

## Fenwick Tree
To balance between the running time of query and update, one data structure called **Fenwick tree** does really well, and gives `O(logn)` time for both query and update.

TODO

### Implementation

type FenwickTree struct {
	tree []int
}

func lowbit(x int) int {
	return x & (-x)
}

func (ft *FenwickTree) Init(n int) {
	ft.tree = make([]int, n+1)
}

func (ft *FenwickTree) Update(idx int, delta int) {
	// 0-indexed -> 1-indexed
	idx += 1

	n := len(ft.tree)
	for idx < n {
		ft.tree[idx] += delta
		idx += lowbit(idx)
	}
}

func (ft *FenwickTree) _rsq(idx int) int {
	sum := 0
	for idx > 0 {
		sum += ft.tree[idx]
		idx -= lowbit(idx)
	}

	return sum
}

func (ft *FenwickTree) RSQ(l, r int) int {
	// 0-indexed -> 1-indexed
	l, r = l+1, r+1

	return ft._rsq(r) - ft._rsq(l-1)
}

## Application

### Total finish time of round-robin execution

Given `n` tasks, and an array `T` of size `n` (where `T[i]` is the number of time units for task `i` to complete).

There is only one worker working on these tasks, and the worker will do the first task for exactly `1` unit of time, then move on to do the second task for exactly `1` unit of time, and so on. If a task is already completed, skip it.

Please give an efficient algorithm to compute the sum of finish time of all tasks. (The finish time is the time from begining to when the task is finished)

#### example
For example, `T = [3, 1, 2]`. We will first pick the first task and run it for exactly one unit of time, so will have `T = [2, 1, 2]`, then do the same to the second task and have `T = [2, 0, 2]`, then do same to the third task and have `T = [2, 0, 1]`.
Repeat the above process until all tasks are finished. So in the end, it taks `6` units of time to finish the first task, `2` units of time for the second task, and `5` unit of time for the third task. Hence we should output `6+2+5=13`

#### Constrain
- `1 <= n <= 10^5`
- `1 <= T[i] <= 10^4`

#### [Idea](https://stackoverflow.com/questions/76123501/find-the-total-turnaround-time-of-n-processes-in-on-time)

#### Solution

func slow(T []int) int {
    // O(n^2)

    n := len(T)

    ans := 0
    for i := range T {
        t := T[i]

        for j := 0; j <= i; j++ {
            ans += min(t, T[j])
        }

        for j := i + 1; j < n; j++ {
            ans += min(t-1, T[j])
        }
    }

    return ans
}

func computeTotalTurnaroundTime(T []int) int {
    // O(n * log(max(T)))

    n := len(T)

    maxT := 0
    for _, t := range T {
        maxT = max(maxT, t)
    }

    // What's the sum of values <= T[i] in A[:i]
    prefixSum := fenwick.FenwickTree{}

    // What's the count the value > T[i] in A[:i]
    prefixCount := fenwick.FenwickTree{}

    prefixSum.Init(maxT + 1)
    prefixCount.Init(maxT + 1)

    totalTurnaroundTime := 0

    // compute the time that task i waiting tasks 0 to i-1
    for _, t := range T {
        totalTurnaroundTime += prefixSum.RSQ(0, t)
        totalTurnaroundTime += prefixCount.RSQ(t+1, maxT) * t

        prefixSum.Update(t, t)
        prefixCount.Update(t, 1)
    }

    // What's the sum of values <= T[i]-1 in A[i+1:]
    suffixSum := fenwick.FenwickTree{}

    // What's the count of values > T[i]-1 in A[i+1:]
    suffixCount := fenwick.FenwickTree{}

    suffixSum.Init(maxT + 1)
    suffixCount.Init(maxT + 1)

    // compute the time that task i waiting tasks i+1 to n-1
    for i := n - 1; i >= 0; i-- {
        t := T[i]

        totalTurnaroundTime += suffixSum.RSQ(0, t-1)
        totalTurnaroundTime += suffixCount.RSQ(t, maxT) * (t - 1)

        suffixSum.Update(t, t)
        suffixCount.Update(t, 1)
    }

    // add the running time of each task
    for _, t := range T {
        totalTurnaroundTime += t
    }

    return totalTurnaroundTime
}

### [Count of Smaller Numbers After Self](https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/)

A typical use of Fenwick tree is to sum the count of numbers in a range.

For example, `A = [1, 19, 2, 5, 5, 4, 0]`, we want to know the count of numbers `<=10`, so we can use Fenwick tree to compute.

### [Reverse Pairs](https://leetcode.com/problems/reverse-pairs/description/)

However, **it will require a large amount of memory if the number range is large.**

For example, `A = [1, int(1e11)]`, althought the size of the `A` is only `2`, it requires an array of length `int(1e11)` to build the Fenwick tree !

A way to optimize the space complexity
- sorting the numbers
- using a hash table to **remap the number to `1 to n`**.

Take the example `A = [1, 19, 2, 5, 5, 4, 0]`, if we want to get the count of number `<= 10`.

we first sort `A` to become `A = [0, 1, 2, 4, 5, 5, 19]` and give each number an id `{0: 0, 1: 1, 2: 2, 4: 3, 5: 4, 19: 5}`.

Then we can binary search the smallest id `i` such that `A[i] > 10`. Then we query the Fenwick tree about the sum in `A[:i]`.

## Ref
https://www.youtube.com/watch?v=WbafSgetDDk

###### tags: `Data Structure`