How to do range update and range query simultaneously?

general
1

I need a way to find solve this :

Given array, use one of two operations. add k to all elements in a given interval, find sum of values in a given interval (both range update and range query simultaneously). I know how to do it using Fenwick tree data structure. I need it using segment tree. Can any one please provide a link to a tutorial?

in reference to the problem : http://www.spoj.com/problems/HORRIBLE/

Can it be done without lazy propagation?

p.s. I found this simple solution http://codeforces.com/blog/entry/6415. Can anyone explain it a bit please? I am confused with two variables in the segment tree. Please help

2

use the above link for the basic idea about the segment trees useful for range queries and the next link for lazy propagation in the segment trees which is useful for the range updates.

1 Like
3

Hey, can this be done without lazy propagation? I am not worried about strict time limit.

4

Hi dragonemperor,

if you are not worried about time limit then :

all type of problem which are solved by lazy propagation can be definitely solve by segment tree because lazy propagation concept is introduced due to high time complexity of segment tree so your update will take O(n) and query take O(long(n)) because updating tree is like updating array you have to update all children + parent node within that range means you have to update each single element within range as you do update in binary search tree and store sum in parent node i.e it will not make any sense :frowning:

1 Like