444iq's blog

How to apply segment tree when you have a modifiable array.
By 444iq, history, 5 years 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

Comments Comments (9)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use an implicit treap to solve this problem.

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

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

→ Reply