Merge Sort Tree (and similar stuff)

Правка en2, от Abito, 2023-11-11 20:24:28

Sometimes I encounter a type of range queries that I don't know how to do using segment tree, so I use a merge sort tree instead. It can answer queries in $$$O(log^2 n ) $$$. I decided to share this because it can be useful to many in contests. First, we know that a node in a segment tree stores the answer for a range of length $$$2^x$$$ for some $$$x$$$, but we can also store in it all the elements in the range sorted in a vector (using merge sort algo) or set or whatever. Here I am going to give a few examples how we can use this to our advantage.

Problem 1: Static Count of Lesser Elements range queries.

We are given an array $$$a_1, a_2, a_3... a_n$$$ and an integer $$$q$$$. The $$$i$$$_th of the next $$$q$$$ lines has three integers $$$l_i , r_i , x_i$$$. The answer for this query is how many $$$a_j$$$ such that $$$l_i \le j \le r_i$$$ and $$$a_j < x$$$.

Solution
Code

Problem 2: Dynamic Lower Bound problem.

We are given an array $$$a_1, a_2, a_3... a_n$$$ and an integer $$$q$$$. The $$$i$$$_th of the next $$$q$$$ lines has an integer $$$t_i$$$, describing the type of query.

  • If $$$t_i = 0$$$ then you are given two other integers, $$$idx_i$$$ and $$$x_i$$$, meaning that we should make $$$a_{idx} = x_i$$$.
  • If $$$t_i = 1$$$ then you are given three integers $$$l_i, r_i, x_i$$$. You should answer with the smallest value $$$v$$$ in the range $$$[l_i,r_i]$$$ such that $$$x \le v$$$. If there is none, print -1.
Solution
Code

Final notes

There are many other things that you can do using technique. You can even solve the dynamic version of the first problem using indexed_set. However you should use this only when you're desperate because it's really slow. Yes it's $O(nlog^2n) but the constant factor is very high because it's segment tree + sets. If you have intereseting problems to add to the blog, or you notice some mistake please say inthe comments. Good luck everyone!

Теги merge sort tree, range queries, segment tree, sets

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский Abito 2023-12-13 13:50:17 72
en5 Английский Abito 2023-11-16 23:38:49 116
en4 Английский Abito 2023-11-12 12:16:05 92
en3 Английский Abito 2023-11-11 21:04:15 2
en2 Английский Abito 2023-11-11 20:24:28 12 Tiny change: 's $O(log^2 n) because w' -> 's $O(log^2n)$ because w'
en1 Английский Abito 2023-11-11 20:22:36 7126 Initial revision (published)