thaonguyendethuongvai's blog

Need help to find a data structure that can solve this operation
By thaonguyendethuongvai, history, 3 days ago, In English

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!

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

https://cp-algorithms.com/data_structures/treap.html

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    but it's very hard

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      if you just want to delete elements, you can also just use a segment tree in this way:

      1. Build segment tree on original array. Store an additional variable at every position (initially 1 for all positions as they are undeleted). Make your segtree support sum queries for this variable.
      2. When you delete some element, toggle it to 0 and set it's value to the identity element wrt the monoid (0 for sum, inf for max, etc).
      3. Now, the i'th undeleted element at any point of time can be found either by "descent on segment tree" or binary search (first position at which prefix sum of additional variable = i).
      4. Answer queries.
      → Reply
    • »
      »
      »
      45 hours ago, # ^ |
        Vote: I like it +60 Vote: I do not like it

      That's what she said.

      → Reply
  • »
    »
    44 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you :D

    → Reply
»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

you can just replace that element, with something that will not afect your answear like for sum 0, min a bug numebr etc

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 unalive in this comment.

    → Reply
    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      yes, that is what i was about to say next,that there may be indexing problems, good point

      → Reply
    • »
      »
      »
      43 hours ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I would have never found his comment, thanks

      → Reply
»
2 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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/45P95CFH

→ Reply
»
35 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

You can combine walk on Segment tree or fenwick tree to be able to manage the indexes when deleted.

→ Reply