Data Structure: Fenwick Tree and Range Update

Something led me to read up on Fenwick Tree (a.k.a Binary Indexed Tree). There are lots of great tutorials that explain what this data structure is, and how it is useful. A google search is all you need. I would like to write up some short discussion on the tree, and also about a technique that is used to allow this tree to support range updates.

Conveyor Belts (Codeforces Round 278 Div. 1 Problem D)

Problem Statement:
Codeforces 278 Div. 1
D. Conveyor Belts

Solution:
What a challenging problem, I could never imagine solving this kind of problem during a real contest. Cool people, cool stuff, cool problem. Let's keep learning!

The problem is actually a range minimum query (RMQ) problem and hence solvable using any data structure that can efficiently compute such queries (\(O(N\lg{N})\) segment tree, \(O(\sqrt{N})\)  square root decomposition, and the like). How can we model this as a RMQ problem?

a bit of data structure: Segment Tree

This data structure is used to efficiently support queries which request for the index of the minimum element in a given range.

The idea is using a divide and conquer: given a range \((i, \ldots, j)\), and then we find the index to the minimum element for \((i, \ldots, \frac{i+j}{2})\) and \((\frac{i+j}{2}+1, \ldots, j)\) seperately, and finally combine the result by choosing the lower element of the two indexes as the minimum index for \(i, \ldots, j\).

The tree is built on a one dimensional array just like Binary Heap and it requires \(O(4N)\) space. To process a query, we traverse down the tree to find the sub-interval which lies totally inside the query range.

Using Segment Tree we can maintain a dynamically changing information on a static data structure as update operations can be implemented efficiently. Furthermore, to increase its performance, we can opt to have a lazy propagation of updates, by maintaining an extra array that mark whether a segment have to be updated or not.

Here is a quick implementation in C/C++ :

vector<int> stree(4*N + 1,0);
vector<int> arr(N + 1,0);

int build(int i, int j, int k)
{
 if(i == j)
 {
  stree[k] = i;
  return stree[k];
 }
 int mid = (i+j)/2;
 int left=-1,right=-1;
 left = build(i,mid,2*k);
 right = build(mid+1,j,2*k+1);
 if(arr[left] > arr[right])
  stree[k] = right;
 else 
  stree[k] = left;
 return stree[k];
}

int rmq(int p, int i, int j, int L, int R)
{
 //invalid query
 if(i > R || j < L) return -1;
 if(i <= L && R <= j) return stree[p];
 int mid = (L+R)/2;
 int left = rmq(2*p, i, j, L, mid);
 int right = rmq(2*p + 1, i, j, mid+1, R);
 if (left == -1) return right;
 if (right == -1) return left;
 return (arr[left] < arr[right]) ? left : right;
}