Hi Codeforces! I wonder that is there any data structure or some implementation of segment tree that has a ability to solve the following operation : - Totally delete an element from the initial array. - Query the maximum / minimum / sum / ... in a range. Example : Initial array : 1 2 3 4 5 - Query for the sum of the range [ 1, 3 ] : 1 + 2 + 3 = 6. - Deleting 1 from the array Now the array is : 2 3 4 5 - Query for the sum of the range [ 1, 3 ] : 2 + 3 + 4 = 9. I 'm just a newbie in cp, sorry for my bad english. Thanks in advance!
https://cp-algorithms.com/data_structures/treap.html
but it's very hard
if you just want to delete elements, you can also just use a segment tree in this way:
That's what she said.
you can just replace that element, with something that will not afect your answear like for sum 0, min a bug numebr etc
That's incorrect because, for instance, if we remove the first elements and then query the sum of the segment [0...3], the query [0...3] will only return the sum of the first two elements instead of the first three. The correct query would be for the segment [0...4]. Therefore, we still need a way to identify which segment needs to be queried. The correct approach is the one mentioned by DNR in this comment.
yes, that is what i was about to say next,that there may be indexing problems, good point
I would have never found his comment, thanks
I think the simplest solution is using something like sqrt-decomposition. (https://cp-algorithms.com/data_structures/sqrt_decomposition.html)
Divide an array into $$$k$$$ blocks and precalculate answer in block.
To delete an element, you need to find his block and his position in block and just erase. After that, recalculate block's answer.
To answer the query, you should find position of left and right elements of the query and then answer like in sqrt-decomposition.
Here is a code: https://pastebin.com/m4s37RdD
But for more hard queries, you can use, for example:
ok thanks bro
You can use a segment tree for that.
Build a segment tree on the original array. When deleting an element set it to an identity(a value that doesn't affect the answer, e. g. 0 for sum, -inf for max).
To maintain the indexes we will use a GNU PBDS
ordered_set, initially let's add all the values from $$$[0;n)$$$ to the set. After removing an element we'll remove its index from the set as well. Now when we want to perform an operation on $$$[l;r]$$$, we'll perform that operation on $$$[\text{*index_set.find_by_order}(l);\text{*index_set.find_by_order}(r)]$$$, same thing applies to indexes for the deletion operations.I think this approach is easier than using cascade descent as other commenters have suggested. Hope this helps.
You can combine walk on Segment tree or fenwick tree to be able to manage the indexes when deleted.
ok thanks :D
thanks me may a