kowalsk1's blog

Adapting BIT to offline type problems
By kowalsk1, history, 6 years 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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years 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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it can be done with a bit offline:

offline calculate for each querry at which position it will be in the complete list after all updates. then replay all queries and use those precalculated indices instead of the real ones.

→ Reply