Chtholly Tree

2019-3-7 created by AD1024

Introduction

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:

• Set numbers in an interval $[L,R]$ to $v$;
• Add $v$ to numbers in an interval;
• Query sum of numbers in an interval;
• Query the $k^{th}$ smallest number in an inverval
• Query the max / min number in an interval

Concept of Chtholly Tree

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]$.

Core Operation - Split

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(AVL) to store the data. In order to quickly find the interval containing $x$, we can use lower_bound function, whose complexity is $O(\log n)$. As defined in the structure of the tree node, the intervals will be sorted by their left end points in the ascending order. By applying lower_bound, we can find the interval which has the smallest left point $L$ such that $L \geq x$.

Then we can destruct the split operation into two conditions:

1. If $x$ is a left end point, we don’t need to split it; so we just return the result we find.

2. 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;
}

Utilize Split

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 an Interval

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

Adding value to 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;
	}
}

Query Maximum

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;
}

Query Kth Smallest Number

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;
}

TLE Warning!!!

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.

Proof of Compexity

I don’t know how to prove. Please teach me!!