oversolver's blog

By oversolver, 3 years ago, In English

TL;DR: range_sum_range_add with only two BITs.

Suppose we have (sub)task to proceed following queries:

  • range_sum(l, r)
  • range_add(l, r, x)

Most familiar solution is segment tree with lazy propagation. And maybe you didn't knew, but such segment tree does not needs pushes!

code of segment tree without pushes

Every time I see segment tree with pushes in this problem, my heart is bleeding... But! This is unnecessary, because this problem does not needs segment tree!

Reducing range_sum_range_add to range_sum_position_add

All following is described in 1-index numeration, and by range I mean half-interval $$$[L, R)$$$.

Let me remind you that sum on range can be reduced to sum on prefix (or suffix). And in the same way — adding on range can be reduced to adding on prefix (or suffix).

How?

OK, suppose we have some changes of array (adding on prefix). We have for each $$$i$$$ value $$$a_i$$$ means this value is added on $$$i$$$-th prefix. How to calculate sum on particular prefix $$$k$$$? All added values inside prefix, i.e. $$$i \leq k$$$, must be added fully as $$$a_i \times i$$$. Values outside prefix, i.e. $$$k < i$$$, must be added as $$$a_i \times k$$$.

Lets keep two classic range_sum_position_add data structures. First, call it f, takes $$$a$$$ as is. Second, call it t, as $$$a_i \times i$$$. It means, if we need to proceed adding $$$x$$$ on prefix $$$i$$$, we call f.position_add(i, x) and t.position_add(i, x*i).

To answer prefix sum query we need:

  • all values inside: it will be t.range_sum(1, i+1),

  • all values outside: it will be f.range_sum(i+1, n+1) * i.

That's all! With help of Binary Indexed Tree, as most popular rsq, we can achieve fast, non recursive and short way to implement required data structure.

We can change prefix/prefix to other three combinations and get similar formulas. As example, my code library have prefix/suffix version to achieve only prefix summation and suffix addition in both nested BITs:

code

Bonus: sqrt versions

It is well-known that with classic sqrt-decomposition queries can be proceeded in $$$O(\sqrt n)$$$ each. But with described reducing to range_sum_position_add we can achieve $$$O(1)$$$ / $$$O(\sqrt n)$$$ or $$$O(\sqrt n)$$$ / $$$O(1)$$$ versions for range_add / range_sum.

First is simple, adding to one element followed with adding to block contain this element, and summation is sum of $$$O(\sqrt n)$$$ blocks and sum of $$$O(\sqrt n)$$$ corner elements.

Second needs reducing range_sum_position_add to position_sum_range_add: lets support suffix sums (which gives sum on range as difference of two suffixes in $$$O(1)$$$) and changing one element $$$i$$$ affecting only suffixes sums from $$$0$$$ to $$$i$$$ (this part takes $$$O(\sqrt n)$$$).

  • Vote: I like it
  • +53
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Cool post, but the trick isn't new, Petr described it in 2013. Sorry to kill the fun :/

https://petr-mitrichev.blogspot.com/2013/05/fenwick-tree-range-updates.html

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    yeah, I remember this post and discussion on cf, but it was like "magic code without description", now I understand this trick more generally.

»
3 years ago, # |
Rev. 6   Vote: I like it +5 Vote: I do not like it

Nice trick. Some steps seams to be missing. One those things is: how to get final answer to L,R query after number of sum updates. Right before "That's all!" part. What should we do with t and f?

Should the the answer be: ans = initial + updates = (pref[r] — pref[l-1]) + ...? I got it in 20 minutes, but it would be nice to have it with explanation: that you need f(i+1, n+1) * i — t(1, i+1) and why. And maybe, maybe, maybe some good self-explanatory naming for f(l,r) and t(l,r), if you care.

Oh, no, ans is a little bit more complicated: updates = f(r+1, n+1) * (r + 1) + t(1, r) — (f(l+1, N+1) * (l +1) + t(1,l) ).