RMQ using two fenwick trees (binary indexed tree)

Question

Based on this paper, I found that it is quite brilliant to use two BITs to do RMQ in O(lg N), as it is easier to code than segment tree, and the paper claims it performs better than other data structures as well.

I understand how to build the tree and how to do query operation, yet I am confused about the update operation. Here's the quotes:

We make the following observation: when we generate the associated intervals of the nodes we pass by, we can cover the whole interval [ p + 1, y ] by starting from node p + 1 and climbing the first tree (Fig. 2.1). So instead of doing a query for every node we update, we compute the results of the queries on the fly by climbing the tree once.

Analogously, we can update all the intervals of the form [ x, p – 1] by starting from node p – 1 and climbing the second tree (Fig. 2.2). The same algorithm is applied for updating both trees.

I suspect it should be the other way round: for finding minimum of interval [p+1, y], we should use the second tree instead of the first one; for finding minimum of interval [x, p-1], we should use the first tree instead.

My question is: Am I correct? If no, can someone give a simple example to demonstrate how the update operation works?

Answer 1

The explanation is a bit ambiguous. I guess they've meant that for [p+1,y] you climb the first three starting from p+1, but use the second tree to query.

Let's imagine that you update value at 10-th index (from the paper). You will have to answer queries for [x, 10 - 1] & [10 + 1, y] while updating the trees. In order to do this efficiently you build two "climbing" lists:

CLB1 by climbing the first tree from p+1: {11, 12}, which correspond to the next intervals: [11..11], [12..15] of the second tree

CLB2 by climbing the second tree from p-1: {9, 8}, which correspond to the next intervals: [9..9], [1..8] of the first tree

Now you start the update of the first tree by climbing up the first tree starting with 10.

10 - trivial update

12 - you need to query [9..9], {10}, [11..11], {12}. You have an answer for [9..9] from the BIT1 by taking the first member of CLB2. And you have an answer for [11..11] from the BIT2, by taking the first member of CLB1. {10} and {12} are trivial.

16 - you need to query [1..9]. {10}, [11..15] (no {16} as it is fictive). You are taking [1..9] from BIT1 by taking first two items of CLB2. You are taking [11..15] from BIT2 by taking first two items of CLB1. {10} is trivial.

As you can see for the left queries you take answers from the first tree using the climbing history from the p-1 of the second tree. For the right queries you take answers from the second tree using the climbing history of p+1 of the first tree.

Similar process is used for updating the right tree.

Update: process for 9th node

In case of updating 9-th index we have next CLBs:

CLB1: {10, 12}, intervals: [10..11], [12..15] of BIT2.

CLB2: {8}, intervals: [1..8] of BIT1

Updating BIT1:

9 - trivial

10 - trivial (we need only {9} and {10})

12 - we need first entry from CLB1 - [10..11], and {12} with {9}

16 - we need two first entries from CLB1 - [10..11] U [12..15], first entry from CLB2 - [1..8] and {9}

Updating BIT2:

9 - trivial

8 - we need first two entries from CLB1 - [10..11] U [12..15] and {9} with {8}

0 - we need first two entries from CLB1 - [10..11] U [12..15] and first entry from CLB2 - [1..8] and {9}