Using Binary Indexed Trees to efficiently do range updates and range MINIMUM queries

Question

It is already known that you can use two BITs (aka Fenwick Trees) to do RMQ in $O(logn)$ and point update in amortized $O(logn)$ time (Described in this paper.)

However, I want a step further, doing range updates: increase all elements in the range from $l$ to $r$ by $k$ ($k$ can be negative).

Is this already achieved or is it not possible yet? Or is it just not for real purposes and is only purely theoretical?

Answer 1

It can be done using dynamic programming over full binary tree. In olympiad community it is often called segment tree, or interval tree, or range tree. All these terms however have other meanings in classic literature.

The brief idea is the following. Every leaf corresponds to an element of the array, while root and every internal vertex corresponds to all leaves in its subtree. Then to update a single element value you need to update the corresponding vertex and all its ancestors.

For RMQ you need to take into account up to 2ドル\log_2 n$ vertices. Just take two sentinels one to the left of the first element, and the other to the right of the last element. (Yes, we need to have extra vertices before and after element of the array, or work carefully with possible fake vertices.) While there is at least one vertex between sentinels do the following: if the left sentinel is left son of it's father, take into account its sibling, and the same for the right sentinel if it is right son of it's father; after that sentinel fathers become new sentinels.

For range updates (which could be either increasing all elements by the same value, or setting all elements to the same value, or some other) we may allow some vertices (including leaves) to have a wrong value, which however could be fixed (updated) in $\mathrm O(\log n)$ of time.

Then for any query (including range update) we firstly need to update the value of leaves used (that are either an element itself for a single element query or both sentinels for a range query) and their ancestors. Luckily all ancestor values will be updated together with leaf value. Going from root down to the leaf (not including the leaf) we compute $\delta = f(v) - \min\{,円f(\ell_v), f(r_v),円\}$, where $v$ is the current vertex, $f(u)$ is value of vertex $u$, $\ell_v$ and $r_v$ are left and right sons of $v$. This $\delta$ corresponds to cumulative update that has reached $v$ but didn't reach its descendants. Then we update both sons: $f(\ell_v) \gets f(\ell_v) + \delta$ and $f(r_v) \gets f(r_v) + \delta$ and continue to the corresponding son. Note that updating vertex and all its ancestors we update also siblings of ancestors.

Then range update query becomes very similar to RMQ. The main difference is that siblings of sentinels should be not taken into account, but updated. Every leaf value in subtree of such a sibling should be increased by $k$, therefore sibling's value also should be increased by $k$. But the sibling is the only vertex of its tree that we update right now. And this update will be casted down later when needed. That's how we do range update using $\mathrm O(\log n)$ of time. Another difference from RMQ is that sentinel value should be updated once again after coming to is from son, because son's sibling could get and update. Also we should stop only after updating the root, not earlier, but do not update sibling if it is a sentinel, too.

It is possible to implement this idea for RMQ using less than 2ドルn$ elements of the basic type (however the most straightforward implementation using array would need up to 4ドルn$ elements). For other type of computation in range queries (like sum, or sum of squares, or sum of pairwise products) or/and for allowing multiple range updates you may need either additional tricks or extra memory for service information. But this idea may be extended to many different application.

• Fam: Oh, thank you, I already know about the segment tree data structure and advanced versions of it, but I just barely see anyone talk about the BIT tree and I don't know any modified version of it beside RUQ+RSQ and PUQ+RMQ, so I asked if a version of RUQ+RMQ were found impractical, after all. I have asked a new follow-up question here, you can read it if you're interested.