Range update and query on a non-standard array

general
,
1

I have an array arr[] of size n (<=10^5) and I have to do range update and query over it.

Problem is, the update has to happen according to an update multiplier array mult[]={c_0,c_1,c_2, …} such that if I add k on arr[a] to arr[b], then

arr[a] = arr[a]+k*c_a
arr[a+1] = arr[a+1] + k*c_(a+1)
.
.
.
arr[b] = arr[b] + k*c_b

I have to do lazy update. What will the update function be like?

2

in each segtree node keep 3 variables

Sum_Of_Arr

Lazy

Sum_Of_Mult

while updating , if current node is completely inside the update range just do lazy += k , while doing the push() operation in segtree , do sum_of_arr += lazy * sum_of_mult , and propogate lazy to the children.

2 Likes