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