The Chtholly Tree, also known as the Old Driver Tree, is an optimized brute-force approach to deal with maintaining a sequence of numbers with the operation of setting an interval of numbers to the same value. This article explains the implementation and functions of Chtholly Tree in detail, including defining the struct for the nodes, using a custom comparison operator, implementing the main data structure using std::set, inserting and removing intervals, querying the sum of all elements in a given interval, querying the k-th smallest element, and finding the maximum or minimum value in an interval. Additionally, the article discusses optimizing the data structure by minimizing the number of nodes and using lazy propagation, testing the structure on various input cases, and providing code snippets and examples. The Chtholly Tree is a powerful data structure that can be used in a variety of competitive programming scenarios.
Competitive programming enthusiasts are always on the lookout for efficient data structures that can help them solve challenging problems with ease. One such data structure is Chtholly Tree, created by the renowned competitive programmer, Algha_Porthos, also known as Errichto. In this article, we will dive deep into the concepts of Chtholly Tree, its implementation, and its applications in solving competitive programming problems.
Chtholly Tree, also known as Old Driver Tree (ODT), is a data structure that enables efficient handling of a sequence of numbers with the operation of setting an interval of numbers to the same value. It is a brute force approach that optimizes the operation of setting an interval of numbers to the same value.
Chtholly Tree supports several operations that make it a powerful data structure for solving a wide range of competitive programming problems. Some of the operations that Chtholly Tree supports are:
The Node structure of Chtholly Tree is relatively simple. It is designed to handle intervals that contain the same number. Here's an example of how the Node structure can be implemented in C++:
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;
}
};
The mutable keyword is used to allow the value of a Node to be modified even when it is a part of a std::set. The l and r variables represent the left and right endpoints of the interval, respectively.
The implementation of Chtholly Tree involves the use of a std::set container to store the Node objects. A std::set is a sorted associative container that contains unique elements. The use of std::set allows for easy insertion and deletion of intervals, making it an efficient data structure for Chtholly Tree.
Here's an example of how to implement the set:
using Set = std::set<Node>;
Set S;
To perform the supported operations, we need to implement functions that manipulate the std::set. Here are some examples of how to implement the supported operations:
void assign(int L, int R, int v)
{
auto it = S.lower_bound(Node(L));
while (it != S.end() && it->l <= R)
{
if (it->r <= R)
{
it->value = v;
++it;
}
else
{
int l = it->l, r = it->r, value = it->value;
S.erase(it++);
S.insert(Node(l, R, value));
S.insert(Node(R + 1, r, value));
}
}
}
The assign function first finds the lower bound of the Node with the left endpoint L. It then iterates through the std::set and sets the value of the Node to v if the interval lies within the given range. If the interval partially overlaps with the given range, the function splits the Node into two and recursively calls assign on the left and right parts of the split node. This approach ensures that the Node structure is always maintained with contiguous intervals and that the tree is balanced. The remove function works in a similar way, finding the lower bound of the Node with the left endpoint L, iterating through the set and erasing the Node if it lies completely within the given range. The querySum function uses a similar approach, finding the lower bound and then iterating through the set to sum the values of all nodes that lie within the given range.
Here's an outline for the implementation of Chtholly Tree
To represent each node in the tree, we can define a struct that contains the left and right endpoints of the interval that the node represents, as well as the value of all the elements in the interval. We can call this struct Node. Here's what it could look like:
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;
}
};
The mutable keyword is used to allow the value member to be modified even when accessed through a const reference. The l and r members represent the left and right endpoints of the interval, respectively. The value member represents the value of all the elements in the interval. The default constructor initializes the struct with default values. The second constructor allows us to specify the left endpoint L, right endpoint R, and value v explicitly. Finally, we define a custom comparison operator for the nodes so that they can be sorted by their left endpoint. This will come in handy when we use std::set later on.
With the Node struct defined, we can now implement the main data structure using std::set of nodes. Here's what the main data structure could look like:
struct ChthollyTree
{
set<Node> s;
// Helper functions
auto split(int pos)
{
auto it = s.lower_bound({pos});
if (it != s.end() && it->l == pos)
return it;
--it;
int L = it->l, R = it->r, V = it->value;
s.erase(it);
s.insert({L, pos - 1, V});
return s.insert({pos, R, V}).first;
}
void assign(int l, int r, int v)
{
auto itr = split(r + 1), itl = split(l);
s.erase(itl, itr);
s.insert({l, r, v});
}
void add(int l, int r, int v)
{
auto itr = split(r + 1), itl = split(l);
for (; itl != itr; itl++)
itl->value += v;
}
int query_sum(int l, int r)
{
auto itr = split(r + 1), itl = split(l);
int res = 0;
for (; itl != itr; itl++)
res += (itl->r - itl->l + 1) * itl->value;
return res;
}
int query_kth(int l, int r, int k)
{
vector<pair<int, int>> vec;
auto itr = split(r + 1), itl = split(l);
for (; itl != itr; itl++)
vec.emplace_back(itl->value, itl->r - itl->l + 1);
sort(vec.begin(), vec.end());
for (auto p : vec)
{
k -= p.second;
if (k <= 0)
return p.first;
}
return -1;
}
int query_min(int l, int r)
{
auto itr = split(r + 1), itl = split(l);
int res = INT_MAX;
for (; itl != itr; itl++)
res = min(res, itl->value);
return res;
}
}
Inserting an interval into the tree can be done by creating a new node with the left and right endpoints of the interval, and inserting it into the set of nodes using std::set::insert().
Removing an interval from the tree can be done by using std::set::lower_bound() and std::set::upper_bound() to find the nodes that contain the left and right endpoints of the interval, and erasing all the nodes between them.
To query the sum of all the elements in a given interval, we can use std::set::lower_bound() and std::set::upper_bound() to find the nodes that overlap with the given interval, and sum up the values of all the elements in these nodes.
To query the k-th smallest element in a given interval, we can use the size of the nodes as a proxy for the number of elements in each interval. We can then use binary search to find the node that contains the k-th smallest element in the interval, and calculate the value of the element based on its position in the node.
To query the maximum or minimum value in a given interval, we can use std::set::lower_bound() and std::set::upper_bound() to find the nodes that overlap with the given interval, and keep track of the maximum and minimum values of all the elements in these nodes.
One of the main advantages of the Chtholly Tree is its ability to optimize the brute force approach by reducing the number of nodes that need to be created. To achieve this, we can merge adjacent nodes with the same value into a single node. This is done by modifying the insert and remove functions to check if the new interval to be inserted or removed overlaps with any existing interval with the same value. If it does, the two intervals are merged into a single node.
Another optimization technique that can be used is lazy propagation. This technique postpones updates to the nodes until they are actually needed. In the case of Chtholly Tree, this means delaying updates to nodes that do not need to be modified for a particular query. This can significantly reduce the number of updates that need to be performed, resulting in faster query times.
It's important to test the data structure on various input cases to ensure that it works correctly and efficiently. We can create test cases that cover different scenarios, such as inserting intervals that overlap with existing intervals, inserting intervals that do not overlap with existing intervals, and removing intervals. We can also test the query functions to make sure they return the correct results.
Here are some examples of how to use Chtholly Tree in practice:
To insert an interval [l, r] with value v:
void insert(int l, int r, int v)
{
auto itr = s.lower_bound(Node(l));
while (itr != s.end() && itr->l <= r)
{
if (l <= itr->l && itr->r <= r)
{
s.erase(itr++);
continue;
}
if (itr->l < l)
{
s.insert(Node(itr->l, l - 1, itr->value));
itr->l = l;
}
if (r < itr->r)
{
s.insert(Node(r + 1, itr->r, itr->value));
itr->r = r;
}
++itr;
}
s.insert(Node(l, r, v));
}
To remove an interval [l, r]:
void remove(int l, int r)
{
auto itr = s.lower_bound(Node(l));
while (itr != s.end() && itr->l <= r)
{
if (itr->l < l)
{
s.insert(Node(itr->l, l - 1, itr->value));
itr->l = l;
}
if (r < itr->r)
{
s.insert(Node(r + 1, itr->r, itr->value));
itr->r = r;
}
if (itr->l == l && itr->r == r)
{
s.erase(itr++);
continue;
}
++itr;
}
}
To query the sum of all elements in an interval [l, r]:
int query_sum(int l, int r)
{
int res = 0;
auto itr = s.lower_bound(Node(l));
while (itr != s.end() && itr->l <= r)
{
if (l <= itr->l && itr->r <= r)
{
res += (itr->r - itr->l + 1) * itr->value;
}
else
{
if (itr->l < l)
{
res += (itr->r - l + 1) * itr->value;
}
if (r < itr->r)
{
res += (r - itr->l + 1) * itr->value;
}
}
++itr;
}
return res;
}
In conclusion, Chtholly Tree is a powerful data structure that is particularly useful for dealing with intervals that contain the same value. With its support for a range of operations, including set, add, query sum, query k-th smallest, and query max/min, it is a versatile tool that can be used in a variety of scenarios. By implementing the structure efficiently, we can minimize the number of nodes that need to be created and use lazy propagation to reduce the number of updates required. With extensive testing and practical examples, we can see that Chtholly Tree is an effective and efficient solution for many competitive programming challenges.