Range update and query without segment or fenwick tree?

general
,
1

Link to problem:

I tried to solve this problem using segment tree with lazy propogation but wasn’t able to get full points because of the huge constraints in the problem(10^7),so finally i read the editorial here


but isn’t getting it and how the concept works.can anyone please explain me how we are maintaining prefix sum’s and getting the max in required range?
Thaks in advance. :slight_smile:
2

You are not asked about max in range.

There is only “max over all array” query at the end.

And idea with prefix sums is quite straightforward. Change every “add on range” query to pair of queries. If you need to add X on [a,b] - it is the same as adding x on [a,n] and -x on [b+1,n]. All new updates have form “add value V starting from position P”. Therefore you may store for every position - how much you need to add starting from this position. Now move over array from left to right and sum up all updates you have. It will essentially tell you value for a given cell.

I’ve just checked editorial at that link, they are doing literally same thing, but in oppisite dirrection:) I believe that my explanation sounds easier to understand. At least it is different from one presented there, so maybe you will get at least one of them

BTW, this approach is quite common, it is often used for a different tasks.

1 Like
3

Thanks, i got it…,coded it and got AC :slight_smile: