Chtholly Tree

Introduction

The Chtholly Tree, also known as the Old Driver Tree (ODT), originated from CF896C.

This name refers to a technique that maintains amortized color segments using a balanced tree (std::set, std::map, etc.) or a linked list (std::list, a manually implemented linked list, etc.), rather than to a specific data structure. Its core idea is to merge a consecutive interval of equal values into one node for processing. Compared with traditional data structures such as segment trees, for problems involving interval assignment operations, a Chtholly Tree makes it more convenient to maintain a value of each covered interval.

Implementation (std::set)

Node type

struct Node_t {
  int l, r;
  mutable int v;

  Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}

  bool operator<(const Node_t &o) const { return l < o.l; }
};

Here, int v is additional data specified by you.

What does the mutable keyword mean?

mutable means “modifiable”, allowing us to modify a value of v in later operations. In C++, mutable is provided to get around the restrictions of const. A variable qualified with mutable (which can only be used for non-static data members in a class) always remains modifiable, even inside a const function.

This means that we can directly modify an element already inserted into set, changing its v value, without removing the element and inserting it into set again.

Node storage

We want to maintain all nodes so that the left endpoints of the intervals they represent are monotonically increasing and no two intervals intersect; ideally, we also want to ensure that the union of all intervals is one maximally long continuous range. Here, take std::set as an example and use a set<Node_t> odt; to maintain all nodes.

During initialization, insert a very long interval into the Chtholly Tree (for example, if the problem requires maintaining positions $1$ through $n$, insert an interval $[1,n+1]$).

The split operation

The split operation is the core of the Chtholly Tree. It takes a position $x$, splits an interval originally containing point $x$ (let it be $[l, r]$) into two intervals $[l, x)$ and $[x, r]$, and returns an iterator pointing to the latter.

Reference code:

auto split(int x) {
  auto it = odt.lower_bound(Node_t(x, 0, 0));
  if (it != odt.end() && it->l == x) return it;
  --it;
  int l = it->l, r = it->r, v = it->v;
  odt.erase(it);
  odt.insert(Node_t(l, x - 1, v));
  return odt.insert(Node_t(x, r, v)).first;
}

On compilers that do not support using auto for return type deduction, change the function's return type to set<Node_t>::iterator.

The assign operation

Another important operation is assign, which assigns a value to an interval. Suppose that interval $[l,r]$ is to be assigned a value $v$.

First, extract interval $[l, r]$. Call split(r + 1), split(l) in sequence, and denote the iterators returned by them as $itr, itl$. Then the iterator range $[itl, itr)$ points to all intervals contained in $[l,r]$ in the Chtholly Tree.

Next, delete the original information. std::set has a member function erase with a signature like iterator erase( const_iterator first, const_iterator last );, which can remove the elements in the range [first; last). Therefore, call odt.erase(itl, itr); to delete the original information.

Finally, insert the new value for interval $[l,r]$. Calling odt.insert(Node_t(l, r, v)) is sufficient.

Reference code:

void assign(int l, int r, int v) {
  auto itr = split(r + 1), itl = split(l);
  odt.erase(itl, itr);
  odt.insert(Node_t(l, r, v));
}

Why do we need to call split(r + 1) before split(l)?

1. The std::set::erase method invalidates references and iterators pointing to erased elements. Other references and iterators are unaffected.
2. The std::set::insert method does not invalidate any iterators or references.
3. The split operation splits an interval. After calling split(r + 1), $r + 1$ becomes the left endpoint of the right interval of the two new intervals. At this point, split the left interval will necessarily not access an interval whose left endpoint is $r + 1$, so it will not split that interval or erase an interval whose left endpoint is $r + 1$, invalidating the iterator. Conversely, if we call split(l) before split(r + 1), an interval whose left endpoint is $l$ may be erased, invalidating the iterator.

The perform operation

Extract an interval from the Chtholly Tree and operate on it. This is similar to the assign operation, except that an interval is traversed instead of deleted.

Reference code:

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

Such extraction operations should not be overused, as they may make the time complexity incorrect. See the “Complexity analysis” section below.

Implementation (std::map)

Compared with the std::set implementation, the std::map implementation has a simpler split operation. Apart from that, the other operations are no different from those for std::set.

Node storage

Because the intervals stored by a Chtholly Tree are continuous, we do not necessarily need to record the right endpoint. We can use a map<int, int> mp; to store all intervals: its keys maintain the left endpoints, and its values maintain a value from the corresponding left endpoint up to before the next left endpoint.

During initialization, if the problem requires maintaining positions $1$ through $n$, call mp[1] = -1, mp[n + 1] = -1 to indicate that $[1,n+1)$, namely $[1, n]$, is assigned the special value $-1$; an interval $[n+1, +\infty)$ is used as a sentinel and can also be initialized.

The split operation

Reference code: (first version)

void split(int x) {
  auto it = prev(mp.upper_bound(x));  // find an interval whose left endpoint is no greater than x.
  mp[x] = it->second;  // create a new interval and copy a value stored in the previous interval to it.
}

Reference code: (second version)

auto split(int pos) {
  auto it = prev(mp.upper_bound(pos));  // find an interval whose left endpoint is no greater than x.
  return mp.insert(it, make_pair(pos, it->second));
  // create a new interval and copy a value stored in the previous interval to it.
}

Here we use an overload of std::map::insert, iterator insert( const_iterator pos, const value_type& value );. It inserts value at a position as close as possible to immediately before pos. If insertion occurs exactly immediately before pos, its complexity is amortized constant; otherwise, its complexity is logarithmic in the container size.

The assign operation

For the assign operation, we need to delete all interval left endpoints in $[l,r−1]$ and then create a new interval.

void assign(int l, int r, int v) {  // Note that r here is the right endpoint of an interval +1.
  split(l);
  split(r);
  auto it = mp.find(l);
  while (it->first != r) {
    it = mp.erase(it);
  }
  mp[l] = v;
}

The perform operation

void perform(int l, int r) {  // Note that r here is the right endpoint of an interval +1.
  split(l);
  split(r);
  auto it = mp.find(l);
  while (it->first != r) {
    // Perform Operations here
    it = next(it);
  }
}

Implementation (linked list)

The mainstream implementation currently uses a set to maintain nodes, but because the average number of maintained intervals is small, the advantage of a set is not obvious. In contrast, a linked list (or array) can maintain splitting and merging operations more simply.

Node storage

using i64 = int64_t;

struct Block {
  Block *next;  // next node in the linked list
  int l, r;     // interval range
  i64 val;      // value on an interval

  Block(Block *next, int l, int r, i64 val)
      : next(next), l(l), r(r), val(val) {}

  bool operator<(const Block &b) const { return val < b.val; }
} *root;

The split operation

// Return an interval whose left endpoint is mid+1.
Block *split(int mid) {
  for (Block *b = root; b; b = b->next) {  // traverse the linked list
    if (b->l == mid + 1) {                 // left endpoint is mid+1
      return b;
    }
    // Find an interval [l, r] that can contain mid and mid+1, and split it into [l, mid] and [mid+1,
    // r]
    if (b->l <= mid && mid + 1 <= b->r) {
      b->next = new Block(b->next, mid + 1, b->r, b->val);
      b->r = mid;
      return b->next;
    }
  }
  return nullptr;  // not found; return null
}

When operating on an interval, because we cannot maintain only part of an interval, we must split an interval in advance before performing the following operations.

Block *lb, *rb;

// Pre-split to ensure that subsequent operations are inside [l, r].
void prepare(int l, int r) {
  lb = split(l - 1);
  rb = split(r);
}

The assign operation

void assign(int l, int r, i64 val) {
  prepare(l, r);
  lb->r = r;  // change interval [lb.l, lb.r] to [lb.l, r]
  lb->val = val;
  lb->next = rb;  // link [lb.l, r] to the adjacent interval on its right
}

// Note: the memory of deleted nodes is not freed here; add this yourself if needed.

The perform operation

void perform(int l, int r) {
  prepare(l, r);
  for (Block *b = lb; b != rb; b = b->next) {
    // Perform Operations here
  }
}

Complexity analysis

Calling assign on the same interval immediately after perform

Observe that the two split operations add at most two intervals; one assign deletes all intervals in the range and adds one interval, while also traversing the deleted intervals. Therefore, the number of intervals traversed is linear in the number of intervals deleted, and each operation only adds $O(1)$ intervals. Consequently, the number of intervals we operate on is linear in the number of operations (including initialization), and the amortized time complexity is $O(m\log n)$, where $m$ is the number of operations and $n$ is the maximum number of intervals in the Chtholly Tree (we can assume $n\leq m$).

No assign after perform

If specially constructed data is allowed, this can certainly be made to time out: it is enough to create sufficiently many different intervals in the Chtholly Tree and repeatedly traverse them, causing the Chtholly Tree's complexity to reach or even exceed quadratic.

To guarantee the correct complexity, the data must be random. See the proof of the Chtholly Tree's complexity on Codeforces. A more detailed rigorous proof can be found in Complexity analysis of the Chtholly Tree. The conclusion of the proof is that the complexity of a Chtholly Tree implemented with std::set is $O(n \log \log n)$, while that of one implemented with a linked list is $O(n \log n)$.

Exercises

• “Luogu 1840” Color the Axis
• “SCOI2010” Sequence Operations (hack data has been added to the source problem)
• “SHOI2015” Brain Hole Therapy Instrument
• “Luogu 4979” Mine: Collapse
• “Luogu 8146” risrqnis

Further reading

Generalization of the mapping idea of ODT - Luogu Column (luogu.com.cn)

References and notes

• Problem - 896C - Codeforces (origin of the Chtholly Tree)
• CF896C Willem, Chtholly and Seniorious solution - Luogu Column (luogu.com.cn) (std::set implementation reference)
• Map implementation of the Chtholly Tree - Zhihu (zhihu.com) (std::map implementation reference)
• Solution to CF896C — Willem, Chtholly and Seniorious — Luogu Column (luogu.cn) (linked-list implementation reference)
• Codeforces Round #449 Editorial - Codeforces (proof of the Chtholly Tree's complexity)
• Complexity analysis of the Chtholly Tree - Zhihu (complexity analysis of the Chtholly Tree)