跳转至

珂朵莉樹/顏色段均攤

名稱簡介

珂朵莉樹（Chtholly Tree），又名老司機樹 ODT（Old Driver Tree）。起源自 CF896C。

注意，這種想法的本質是基於數據隨機的「顏色段均攤」，而不是一種數據結構，下文介紹的操作是這種想法的具體實現方法。

前置知識

會用 STL 的 set 就行。

核心思想

把值相同的區間合併成一個結點保存在 set 裏面。

用處

騙分。只要是有區間賦值操作的數據結構題都可以用來騙分。在數據隨機的情況下一般效率較高，但在不保證數據隨機的場合下，會被精心構造的特殊數據卡到超時。

如果要保證複雜度正確，必須保證數據隨機。詳見 Codeforces 上關於珂朵莉樹的複雜度的證明。

更詳細的嚴格證明見 珂朵莉樹的複雜度分析。對於 add，assign 和 sum 操作，用 set 實現的珂朵莉樹的複雜度為 \(O(n \log \log n)\)，而用鏈表實現的複雜度為 \(O(n \log n)\)。

正文

首先，結點的保存方式：

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

其中，int v 是你自己指定的附加數據。

mutable 關鍵字的含義是什麼？

mutable 的意思是「可變的」，讓我們可以在後面的操作中修改 v 的值。在 C++ 中，mutable 是為了突破 const 的限制而設置的。被 mutable 修飾的變量（mutable 只能用於修飾類中的非靜態數據成員），將永遠處於可變的狀態，即使在一個 const 函數中。

這意味着，我們可以直接修改已經插入 set 的元素的 v 值，而不用將該元素取出後重新加入 set。

然後，我們定義一個 set<Node_t> odt; 來維護這些結點。為簡化代碼，可以 typedef set<Node_t>::iterator iter，當然在題目支持 C++11 時也可以使用 auto。

split

split 是最核心的操作之一，它用於將原本包含點 \(x\) 的區間（設為 \([l, r]\)）分裂為兩個區間 \([l, x)\) 和 \([x, r]\) 並返回指向後者的迭代器。 參考代碼如下：

1
2
3
4
5
6
7
8
9
auto split(int x) {
  if (x > n) return odt.end();
  auto it = --odt.upper_bound(Node_t{x, 0, 0});
  if (it->l == x) return 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;
}

這段代碼有什麼用呢？ 任何對於 \([l,r]\) 的區間操作，都可以轉換成 set 上 \([split(l),split(r + 1))\) 的操作。

assign

另外一個重要的操作 assign 用於對一段區間進行賦值。 對於 ODT 來説，區間操作只有這個比較特殊，也是保證複雜度的關鍵。 如果 ODT 裏全是長度為 \(1\) 的區間，就成了暴力，但是有了 assign，可以使 ODT 的大小下降。 參考代碼如下：

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

其他操作

套模板就好了，參考代碼如下：

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

注：珂朵莉樹在進行求取區間左右端點操作時，必須先 split 右端點，再 split 左端點。若先 split 左端點，返回的迭代器可能在 split 右端點的時候失效，可能會導致 RE。

習題

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