Query of the range of the cotolly tree chtolly tree old driver tree

Because I haven't seen this animation , So let's make a remark . Kodori is Kodori · Norta · Seneolis , Light novel 《 What are you doing at the end of the day ？ Are you free ？ Can you save ？》 And the heroine in her derivative works , One of the adult demon soldiers . The strongest holy sword “ Seneolis ” Suitable for . The original question is Codeforce A topic related to interval on .Chtholly Tree also called Old driver Tree.

Kodori tree - OI Wiki (oi-wiki.org)

This saw tree structure is not actually a data structure , Just one. set The usage of 21 .

The first is the basic idea , Realize the old driver tree , Just one `std::set` And be familiar with `std::set::upper_bound` And some other features . But some things to note include iterator failures .

The core idea of the old driver tree 、 The core idea of range query

On the scope （ Section ） Keep it in order ; Segment the interval in the process , After segmentation, the original fragmented intervals are deleted in sequence ; Finally, merge a large interval .

Here are some things to note C++ The main points of . The first point is std::set Performance problems of . commonly std::set May be used as a sequential container （ Although the complexity of sequential access is dangerous , But for finding, there are logn Time is very easy to use , That is to say , Occasional content changes ）. `std::set` The participation ranking of is through `operator <` Can provide support .

C++ If you want to modify std::set Medium Element without deleting it and reinserting it （ Delete the rebalance Time consuming ） What to do ？

Use mutable attribute , As long as it's not set The data involved in sorting in the .

Then, how to split the interval . Let's review all kinds of binary search first .

Two point search lower_bound and upper_bound in , How to find the following ：（1） The first one is greater than ,（2） The last one is less than or equal to ,（3） The first is equal to . wait ...

Be careful ,ODT The tree species are of that kind , It depends on the specific situation . Consider here if the last one is less than or equal to . We use it `upper_bound -1` To fulfill this requirement .

For a (l, r) The range of ,

• First , obtain (l+k, ...) k Greater than or equal to 0 Interval iterator for , and (r+k, ...) k Greater than or equal to 0 Interval iterator for
• Then delete all the nodes directly from the two iterators , Then insert a （l,r） The node of .

Then I will add that for the last case less than , If not r, How to split ？

We consider the normal incremental approach , There are already ：

[1, 5] and [10, 16]

Try to split at this time 6,upper_bound-1 Get is [1,5] This interval , The split is actually deleted [1,5] Insert a new [1, 6] node and [6, 5] node .

It's not feasible . So we can only do it in full quantity ！

If there is [1,5] and [10,16], Then we must have （ If boundary yes 20 Words ）：

([1, 5]: true), ([6, 9]: false), ([10, 16]: true), ([17, 20]: false)

This arrangement , So as to ensure that the search 6 When we split up , Will go straight back to 6, because 6 There must be . If 7 non-existent , Then maybe this is the case ：

([1, 7]: true), ([8, 9]: false), ([10, 16]: true), ([17, 20]: false)

namely 6 Must be included by the previous one .

The remaining query has no description , Reading and writing are OK split Set of templates , But the read operation is optimized , For example , lookup 【1,6】, Just read ,6 Nature and 【5,7】 alike , No splitting ：

([1, 2]: true), ([3, 4]: false), ([5, 7]: true), ([8, 20]: false)

Summarize and modify the visited routine template ：

void performance(int l, int r) {   auto itr = split(r + 1), itl = split(l);   for (; itl != itr; ++itl) {     // Perform Operations here   } }

notes ： During the operation of finding the left and right end points of an interval, the Kodori tree , Must first split Right endpoint , Again split Left end point . If first split Left end point , The returned iterator may be in split The right endpoint is invalid , May lead to RE.

set Iterator failure problem for

actual set The iterator of does not fail , Unless you delete him .

To sum up Chtholly Tree The idea of ：

• All intervals regardless of true false Or what nature , Must exist as a whole , So at first it was the whole domain Are of the same nature .
• Every time the interval is modified , Will cause division .
• Interval operation first split The right to split On the left .