Chtholly Tree (aka Old Driver Tree(ODT)) is an optimized brute force approach to deal with maintaining a sequence of number with the operation of setting an interval of number to a same number. In this article, I’ll briefly elaborate how to implement Chtholly Tree and some restriction of this fancy data structure.
Supported Operation:
The way to store the data is quite simple. This data structure is created to deal with intervals that containing the same number. Thus the Node structure can be coded as following.
struct Node {
mutable int value;
int l, r;
Node() {}
Node(int L, int R=-1, int v=0): l(L), r(R), value(v) {}
bool operator < (const Node& o) const {
return l < o.l;
}
}
Intuitively, it maintains the left end point, the right end point and the number in the interval $[L,R]$.
Here is the heart of the data structure, the split(x)
function. It accepts a position $x$ and split the interval $[L,R]$ where $x$ located in to two intervals: $[L,x-1]$ and $[x,R]$.
To maintain the intervals sorted, we use set
Then we can destruct the split operation into two conditions:
If $x$ is a left end point, we don’t need to split it; so we just return the result we find.
Otherwise, the result of lower_bound gives us the interval next to the one we want to split, so we move one step back and then check whether $x$ is in the interval. If it is greater than the right end point, which means $x$ does not fall into the interval, we just return the end of the iterator. Else, the current interval $[L,R]$ satisfies $L \leq x \leq R$, so we can split it into $[L,x-1]$ and $[x,R]$ by removing current interval and insert two intervals. Note that the only thing we care is the interval containing $x$, so we always return the iterator pointing to $[x,R]$.
The code looks like this:
set<Node>::iterator split(int x) {
auto it = tree.lower_bound(Node(x));
if (it != tree.end() && x == it->l) return it;
--it;
if (it->r < x) return tree.end();
int pL = it->l; int pR = it->r; int v = it->v;
tree.erase(it);
tree.insert(Node(pL, x - 1, v));
// this will return the iterator pointing to the
// newly inserted element
return tree.insert(Node(x, pR, v)).first;
}
Split out intervals using a single point dose not make any sense. But given an interval $[l,r]$, if we apply $L=split(l)$ and $R=split(r+1)$, we can get two iterators that contains all the intervals contained by $[l,r]$. The rest of the article will focus on how to exploit the $split$ function.
Flatten means setting numbers in an interval to a same number. Given an interval $[l,r]$, we can perform $split$ on two ends of the interval and then erase all the subintervals; at last we insert a new interval containing the same number.
// Set all numbers in [l,r] to v
void flatten(int l, int r, int v) {
auto L = split(l);
auto R = split(r + 1);
tree.erase(L, R) // erase will remove [L, R) so that's why we are using split(R+1) above
tree.insert(Node(l, r, v));
}
A very brutal solution to flatten intervals
Pretty much similar to that of flattening intervals; instead we just modify values but not erasing them.
// Add v to numbers n [l,R]
void add(int l, int r, int v) {
auto L = split(l); auto R = split(r + 1);
while (L != R) {
L -> value += v;
++L;
}
}
int query_max(int l, int r) {
auto L = split(l); auto R = split(r + 1);
int maxn = -0x3f3f3f3f;
while (L != R) {
maxn = maxn < L -> value ? L -> value : maxn;
++L;
}
return maxn;
}
This is the real fancy brute force I’ve ever seen. First, as usual, we split out $l$ and $r+1$. Then we store all the values and the length of the intervals into pairs and sort the pairs in ascending order. Since we know how many numbers having the same value, we just subtract that from $k$ until $k \leq len$ where $len$ is the length of current interval, and the result is the value of that interval.
int query_kth(int l, int r, int k) {
auto L = split(l);
auto R = split(r + 1);
vector<pair<int, int>> vec;
while (L != R) {
vec.push_back(make_pair(L -> value, L -> r - L -> l + 1));
++L;
}
sort(vec.begin(), vec.end(), [=](auto x, auto y) -> bool {
return x.first < y.first;
});
for (auto v: vec) {
k -= v.second;
if (k <= 0) return v.first;
}
return -1;
}
Note: Chtholly Tree is actually an optimized method to deal with flattening intervals as well as operations querying max / min / $k^{th}$ number. Thus, it requires that in each query $L, R$ have tto be randomly generated.
I don’t know how to prove. Please teach me!!