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.

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

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

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

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.

You can use an implicit treap to solve this problem.

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.

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.

Thanks very much. I don't know what is treap. Can you please give me some good resources from where you studied.

Treap,

Treap

Thanks.

Here is a good video from Algorithms Live.

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

Ok thanks. i also came up with different solution which I mentioned above. But yaa! treaps are very powerful in such cases. Thanks!

Are you talking of this blog.

http://codeforces.com/blog/entry/46507

Yeah, that. I'm modifying it further but that will take time.