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!
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).
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:
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)$$$).
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
yeah, I remember this post and discussion on cf, but it was like "magic code without description", now I understand this trick more generally.
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) ).