tbquan08hanoi's blog

Segment tree with deletion
By tbquan08hanoi, history, 5 months ago, In English

I have heard about segment trees that can handle delete queries by processing the queries offline and creating a segment tree over the timeline of the queries. Does anyone know about this? (It could be persistent segment tree, but i'm not sure. If the structure above does not exist, please tell me.)

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please give the link of the original problem

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

    the editorial uses sqrt decomposition to solve the problem, and i can't just check all submissions, but all submissions i saw used the sqrt method too

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

      ... but i still don't know which problem you're referring to

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

You need to be more clear about what operations the data structure has to support. If you need it to support the deletion of intervals among many other queries and updates that necessitate a segment tree, then a treap (with merge and split operations) is your best bet.

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

Seams like you are talking about this trick: https://usaco.guide/adv/offline-del?lang=cpp

→ Reply