ARRAY QUERIES problem (segment tree)

#1

i am unable to understand the approach to this problem,
i mean how should i make the segment tree, i mean on what basis ,
please guide me
question link: https://hack.codingblocks.com/contests/c/668/560

#2

We can initially compute f(i,k) for all 1<= i <=N . We can build a sum segment tree initially. Now whenever an update comes, we know that each element is added to some f(i,k), for in a range. So we can lazily update at all the positions, i (it will be a range or two ranges). See the code for more clarity.

#3
#4

oh okk got it thanks :blush:

#5

bhaiya in this question i have this small doubt that
in the question is it ( (x+n-1)%n + 1 ) or (x+n-1)%(n+1) ???

#6

sir the code that u gave me for reference is for 0 based indexing
i am not able to find the cyclic update range due to the above confusion so
can u please give me a 1 indexed code

#8

bro just make changes in the array shift everything by one … Its just a normal thing… Try to do this …

#9

bdw it is ( (x+n-1)%n + 1 )

1 Like
#10

ohk…