Binary Indexed Tree (Part 2)

Motivation

Building on ideas from Part 1, in this part, we explore some lesser-known extensions and applications of BIT.

This is by no means a finished post, and I'll keep updating whenever I find new BIT applications/extensions.

Variation 1: Range update, Point query

We want the data structure, which supports the following operations on an input array \(a[1..n]\):

Recall from Part 1, normal BIT only supports range prefix queries and point updates. How are we going to implement point query, range update with existing operations?

Consider the diff array d[1..n], d[1] = a[1], d[i] = a[i]-a[i-1] for i=2,...,n, a[i] = d[i] + d[i-1] + ... + d[1] for i=1,...,n.

The key idea is to use the basic range query-point update BIT on the diff array \(d[1..n]\) instead of the original array \(a[1..n]\).

Clearly, query(i) = sum(d[1..i]) = a[i].

Now think about the range update u(L,R,v), \(a[i] \leftarrow a[i]+v\) for all \(L \leq i \leq R\), how does the diff array change with the update?

Thus we can achieve the range update u(L,R,v) with two point updates:

See also my reference implementation in C++ if you're interested.

Variation 2: Range update, Range query

We want the data structure, which supports the following operations on an input array \(a[1..n]\):

We've seen above how range update can be implemented. Let see how prefix range queries at different \(i\)s change after a range_update(L,R,v), let denote the change to sum(a[1..i]) as \(\delta(i)\)

Note \(\delta(i) = b(i) * i - c(i)\). We can use 2 range update/point query BITs (the variation 1 above) to implement the range query and range update. The first BIT computes \(b(i)\):

$$ b(i) = \left\{\begin{array}{ll} 0 & \text{if}~i < L \\ v & \text{if}~L \leq i \leq R \\ 0 & \text{otherwise} \end{array}\right. $$

The second BIT computes \(c(i)\):

$$ c(i) = \left\{\begin{array}{ll} 0 & \text{if}~i < L \\ (L-1)*v & \text{if}~L \leq i \leq R \\ (L-1)*v - R*v & \text{otherwise} \end{array}\right. $$

range_update(L,R,v) can be implemented as:

# bit1
bit1.point_update(L, v)
bit1.point_update(R+1,-v)
# bit2
bit2.point_update(L, (L-1)*v)
bit2.point_update(R+1, -R*v)

Also, range_query(i) = bit1.query(i) * i - bit2.query(i)

See also my reference implementation in C++ if you're interested.

2D BIT

Consider a 2D grid of size \(H \times W\), we want to support the following operations on the grid in \(O(\log H * \log W)\) time:

As you may expect, the point_update is a straightforward extension of the normal 1D BIT into 2D. The range query can be computed as:

range_query(r1,r2,c1,c2) = range_query(1,r2,1,c2) - range_query(1,r2,1,c1-1) - range_query(1,r1-1,1,c2) + range_query(1,r1-1,1,c1-1)

See also my reference implementation in C++.

Inversion Counting

\(a[1..n]\) is a permutation of \(\{1,2...n\}\). An inversion is a pair \((i,j)\), \(1 \leq i < j \leq n\) such that \(a[i] > a[j]\). Count the number of inversions in \(a[1..n]\).

The key idea is use the values \(a[i]\) as index in BIT.

Below is an overly commented Python snippet:

def count_inversion(a: List[int]) -> int:

  // initialize a BIT of size len(a): bit

  inv_cnt = 0
  for i, x in enumerate(a):
    # bit.query(x) returns how many values added so far, which are smaller than x.
    # Thus i - bit.query(x) is the number of values added which are bigger than x.
    inv_cnt += (i - bit.query(x))

    # It's important to update after the query.
    bit.update(x,1)

  return inv_cnt

Order Statistic Tree

We need a set-like data structure, which supports the following operations:

Constraint: all updates \(x\) are in the range \([1..N]\) for some integer \(N\).

Again, the trick here is to use the element value as index in BIT array, making use of the constraint that all element values are in the range \([1..N]\).