tbquan08hanoi's blog

By tbquan08hanoi, history, 11 days 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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

please give the link of the original problem

  • »
    »
    9 days 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

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

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

»
11 days 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.

»
11 days 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