Adapting BIT to offline type problems

Revision en4, by kowalsk1, 2018-05-25 04:18:12

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 vector. 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.

Tags time complexity, algorithms, offline query, bit/fenwick tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English kowalsk1 2018-05-25 04:18:39 9 Tiny change: 'on on the vector. If it is' -> 'on on the array. If it is'
en4 English kowalsk1 2018-05-25 04:18:12 23 Tiny change: '$ integers and $q$ queri' -> '$ integers, you´re asked to perform $q$ queri'
en3 English kowalsk1 2018-05-25 04:16:47 2 Tiny change: '$ to the $i$-th posit' -> '$ to the $x$-th posit'
en2 English kowalsk1 2018-05-25 04:16:00 79 Tiny change: '------\n\nGiven an i' -> '------\n\n###Given an i' (published)
en1 English kowalsk1 2018-05-25 04:09:15 602 Initial revision (saved to drafts)