Fenwick Tree (BIT)

Question 1

Counting Inversions

Given A[1, n] of n distinct integers, count number of inversions

Answer 1

1. (coordinate compression) Remap values in A to be in the range [1, n] without changing their relative order. Sort the values and replace each of them with its ranking in the sorted array
2. Use a vector B[a, n] and keep a Fenwick Tree on it. Scan A from right to left: add(i, 1) and then sum(i-1) is equal to the number of elements to the right of i that are smaller than i

Θ(nlogn) time with BIT

Question 2

Nested Segments
Given n segments [Li, Ri], for each segment, find the number of segments that are completely contained in the segment. There are no overlapping endpoints.

Answer 2

1. (coordinate compression) Remap endpoints to [1, 2n]
2. Use a Fenwick Tree on B[1, 2n]. B[i] = 1 iff i is right endpoint of still unprocessed segment. Properties of segment completely contained in [L, R]: start > L then not already processed, end < R then sum(R) gives their number
3. Sweep line algorithm to process segments from left to right based on their starting position. Let’s say current segment is [L, R]:
   3.1. Remove its right endpoint from B (set B[R] = 0)
   3.2. Compute sum(R)

Θ(nlogn) time with BIT

Question 3

Update the array
Given A[1, n] initialized to zero, we would like to support
* Access(i) returns A[i]
* RangeUpdate (l, r, v) adds v to A[l], A[l+1], … , A[r]

Goal: queries in Θ(logn) time

Answer 3

Use a vector B (with Fenwick Tree) such that Sum(i) = Access(i) = A[i]

• RangeUpdate (l, r, v): perform Add(l, v) and Add(r+1, -v)
  
  • if 1 <= i < l, Sum(i) is unchanged
  • if l <= i <= r, Sum(i) is +v
  • if r < i <= n, Sum(i) is +v -v = 0

Θ(logn) time with BIT

Question 4

Dynamic Prefix Sums with Range Updates
Given A[1, n] initialized to zero, we would like to support
* Sum(i) returns prefix sums of A[i]
* Add(i, v) performs A[i] += v
* RangeUpdate (l, r, v) adds v to A[l], A[l+1], … , A[r]

Goal: queries in Θ(logn) time

Answer 4

Add(i, v) = RangeUpdate(i, i, v)
Access(i) = Sum(i) - Sum(i - 1)

Store two Fenwick Trees, FT1 and FT2.
FT1 such that Sum(i) = A[i], which means that RangeUpdate (l, r, v) performs Add(l, v) and Add(r+1, -v).
SumFT1(i) * i will give some errors, use FT2 to cancel out.
FT2[l] = -v(l-1)
FT2[r+1] = v(l-1) + v(r-l+1)

Finally, Sum(i) = SumFT1(i) * i + SumFT2(i)

Question 5

Fenwick Tree