Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

k0walsk1's blog

By k0walsk1, history, 7 months ago, In English,

Consider the following problem:

Given an initial array of n integers, you´re asked to perform q queries of the form:

I x V : Add V to the x-th position on the array. If it is not empty (equals 0) then add it between the positions x and x + 1.

S x y : Calculate the sum of all elements from index x to y, inclusively.

My teacher has advised us to use RMQ or an Offline Segment Tree for this one, but i would like to know if there´s a way of adapting the Fenwick Tree to support this sort of shift that may need to be done on the vector efficiently.

 
 
 
 

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by k0walsk1 (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by k0walsk1 (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So I assume that adding the new element between x and x+1 changes the indices of all elements to the right of x.

In that case there is a better data structure to do this rather than segment tree or fenwick (I am not sure if it can be done with those anyway).

It is called Treap.In case you want to learn treap:

See this -- https://threads-iiith.quora.com/Treaps-One-Tree-to-Rule-em-all-Part-1