444iq's blog

By 444iq, history, 7 months ago, In English,

The question is you are given an array A of N integers N<=10^5 and q queries, q <= 10^5.

The are for types of query operation.

  1. 0 x y --> find the sum in the range x to y , 0 based index.

  2. 1 x --> Append element with value x to the end of array.

  3. 2 x ---> Delete element at index x, all the elements from x+1 to n-1 index comes forwards.

  4. 3 x y --> Change A[x] to y.

You have to return answer for all sum queries, that is query 1.

How to solve such problem.

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

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

You can use an implicit treap to solve this problem.

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

    I think, I have a different approach. Let the array size be n+q with all elements 0. now appeding simply means changing last element. deleting means change a[x] = 0 and store the index that is deleted.

    now query in range x to y means number of deletes in range x to y say k. so query becomes x to y + k.

    we can use fenwick tree to count deletes.

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

      Yeah that can also be done. I missed the part about appending in the end. Although personally, I would use an implicit treap, as I have one in my codebook and it is super easy to use.

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

General answer to the title question: Treap treap treap. I implemented one that supports a lot of operations, see my blogs for details.