0
$\begingroup$

I have been given an array of integers of size n and q queries which can be of 2 types:
1.Decrement all elements in the given range by some value
2.Find sum of all elements in the given range
1<=n,q<=10^5
I have tried brute force but it gives TLE
Same goes for prefix sum and even segment trees which improve sum query but slow down updation
I cannot figure out how to update in O(log n)
Would lazy propagation help ?
If not , how else can i proceed with this?
P.S. First timer here . Apologies if i missed out on something

$\endgroup$
2
$\begingroup$

Suppose that your array is $a_1,\ldots,a_n$, but instead of storing it this way, you store the differences $\delta_i = a_i - a_{i-1}$ (where $a_0 = 0$). Decrementing $a_i,\ldots,a_j$ by $x$ is then the same as decrementing $\delta_i$ by $x$ and incrementing $\delta_{j+1}$ by $x$. Querying the prefix sum $a_1 + \cdots + a_j$ (using which you can query the sum of any range) amounts to calculating $$ \sum_{t=1}^j \sum_{k=1}^t \delta_k = \sum_{k=1}^j \sum_{t=k}^j \delta_k = \sum_{k=1}^j (j-k+1)\delta_k = (j+1)\sum_{k=1}^j \delta_k - \sum_{k=1}^j k\delta_k. $$ The idea now is to use a Fenwick tree, which is an array data structure which can perform both element updates and prefix sums in $O(\log n)$. We use two Fenwick trees, one storing $\delta_1,\ldots,\delta_n$ and the other storing $\delta_1,2\delta_2,\ldots,n\delta_n$ (we can in fact merge them into a single Fenwick tree which stores information for both values at every node). Above we have outlined how to perform each of your two queries in $O(\log n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.