Skip to content

Chtholly Tree / Color Segment Amortization

Introduction

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

This name refers to a technique of "using balanced trees (std::set, std::map, etc.) or linked lists (std::list, handwritten linked lists, etc.) to maintain color segments with amortized complexity", rather than a specific data structure. Its core idea is to merge consecutive intervals with the same value into a single node for processing. Compared to traditional data structures like segment trees, for problems involving interval assignment operations, Chtholly Tree can more conveniently maintain the value of each assigned interval.

Implementation (std::set)

Node Type

1
2
3
4
5
6
7
8
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 the additional data you specify.

What does the mutable keyword mean?

mutable means "mutable", allowing us to modify the value of v in subsequent operations. In C++, mutable is used to bypass const restrictions. A variable modified by mutable (mutable can only modify non-static data members of a class) will always be mutable, even within a const function.

This means we can directly modify the v value of an element already inserted into the set, without needing to remove and reinsert the element.

Node Storage

We want to maintain all nodes such that the left endpoints of the intervals they represent are monotonically increasing and pairwise disjoint, and ideally, the union of all intervals is a large continuous range. Here, using std::set as an example, we maintain all nodes with a set<Node_t> odt;.

During initialization, insert an extremely long interval into the Chtholly Tree (e.g., if the problem requires maintaining information from position \(1\) to \(n\), insert the interval \([1,n+1]\)).

split Operation

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

Reference code:

1
2
3
4
5
6
7
8
9
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, you can change the function's return type to set<Node_t>::iterator.

assign Operation

Another important operation: assign. Used to assign a value to an interval. Suppose we want to assign value \(v\) to interval \([l,r]\).

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

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

Finally, insert the new value for interval \([l,r]\). Call odt.insert(Node_t(l, r, v)).

Reference code:

1
2
3
4
5
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 split(r + 1) before split(l)?
  1. The std::set::erase method invalidates references and iterators to the 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 new interval. Then splitting the left interval will definitely not access the interval with \(r + 1\) as its left endpoint, thus not splitting it, and deleting the interval with \(r + 1\) as its left endpoint will not invalidate iterators. Conversely, doing split(l) first, then split(r + 1), might delete the interval with \(l\) as its left endpoint, invalidating iterators.

perform Operation

Extract an interval from the Chtholly Tree and perform operations on it. Similar to the assign operation, but instead of deleting the interval, we traverse it.

Reference code:

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

Note that such extraction operations should not be abused, as they may lead to incorrect time complexity. See the "Complexity Analysis" section below.

Implementation (std::map)

Compared to the std::set implementation, the split operation in the std::map implementation is simpler. Other operations are no different from those in std::set.

Node Storage

Since the intervals stored in Chtholly Tree are continuous, we don't necessarily need to record the right endpoint. We can use a map<int, int> mp; to store all intervals, where the key maintains the left endpoint and its value maintains the value from that left endpoint up to (but not including) the next left endpoint.

During initialization, if the problem requires maintaining information from position \(1\) to \(n\), call mp[1] = -1, mp[n + 1] = -1 to indicate that \([1,n+1)\) i.e., \([1, n]\) are set to a special value \(-1\), and the interval \([n+1, +\infty)\) is used as a sentinel, which can also be initialized.

split Operation

Reference code: (First version)

1
2
3
4
void split(int x) {
  auto it = prev(mp.upper_bound(x));  // Find the interval with left endpoint <= x.
  mp[x] = it->second;  // Create a new interval and copy the value from the previous interval to this one.
}

Reference code: (Second version)

1
2
3
4
5
auto split(int pos) {
  auto it = prev(mp.upper_bound(pos));  // Find the interval with left endpoint <= x.
  return mp.insert(it, make_pair(pos, it->second));
  // Create a new interval and copy the value from the previous interval to this one.
}

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

assign Operation

For the assign operation, we need to delete all interval left endpoints within \([l,r−1]\), then create a new interval.

1
2
3
4
5
6
7
8
9
void assign(int l, int r, int v) {  // Note: here r is the interval right endpoint + 1
  split(l);
  split(r);
  auto it = mp.find(l);
  while (it->first != r) {
    it = mp.erase(it);
  }
  mp[l] = v;
}

perform Operation

1
2
3
4
5
6
7
8
9
void perform(int l, int r) {  // Note: here r is the interval right endpoint + 1
  split(l);
  split(r);
  auto it = mp.find(l);
  while (it->first != r) {
    // Perform Operations here
    it = next(it);
  }
}

Implementation (Linked List)

Currently, the mainstream implementation uses set to maintain nodes. However, since the average number of maintained intervals is small, the advantage of set is not significant. In contrast, linked lists (or arrays) can more concisely maintain split and merge operations.

Node Storage

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
using i64 = int64_t;

struct Block {
  Block *next;  // Next node in the linked list
  int l, r;     // Interval range
  i64 val;      // Value on the 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;

split Operation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// Returns the interval with left endpoint 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 the interval [l, r] that contains both mid and mid+1, 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 intervals, since we cannot maintain only part of an interval, the following operations need to pre-split the interval before performing the corresponding operation.

1
2
3
4
5
6
7
Block *lb, *rb;

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

assign Operation

1
2
3
4
5
6
7
8
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 its right adjacent interval
}

// Note: Memory of deleted nodes is not freed here; add if needed.

perform Operation

1
2
3
4
5
6
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

Observing this case, we find that two split operations add at most two intervals; one assign deletes all intervals within the range and adds one interval, while traversing the deleted intervals. So, the number of intervals we traverse is linear with the number of deleted intervals, and each operation only adds \(O(1)\) intervals. Therefore, the number of intervals we operate on is linear with respect to the number of operations (including initialization). The time complexity is amortized \(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 consider \(n\leq m\)).

Not performing assign after perform

If special adversarial data is allowed, this can definitely be exploited. By creating enough different intervals in the Chtholly Tree and repeatedly traversing them, the complexity of Chtholly Tree can reach or even exceed quadratic.

To guarantee correct complexity, the data must be random. See Proof of Chtholly Tree complexity on Codeforces for details. A more detailed rigorous proof is in Complexity Analysis of Chtholly Tree. The conclusion of the proof is: the complexity of Chtholly Tree implemented with std::set is \(O(n \log \log n)\), while the complexity with a linked list is \(O(n \log n)\).

Exercises

Further Reading

Generalization of ODT's Mapping Idea - Luogu Column (luogu.com.cn)

References and Notes

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用