引言
珂朵莉树（Chtholly Tree，又称ODT — Old Driver Tree）是一种优雅而高效的区间管理数据结构，最早由 Codeforces 用户 Ixiaohao 在2017年提出。它利用数据随机性或操作的特殊分布，以近似 $O(n \log \log n)$ 的均摊复杂度处理区间赋值、区间求和等操作。本文将用Java完整实现珂朵莉树，解析其核心思想与适用场景。
核心思想：基于时间戳的区间分裂
珂朵莉树维护一组互不重叠的连续区间，每个区间具有相同的值。关键操作是 split(pos)：将包含位置pos的区间在pos处切分为两段。配合 assign(l, r, val) 操作——将 $[l, r]$ 内所有区间合并为单一值区间——数据结构的规模被有效控制。
关键假设：区间赋值操作足够随机，或赋值区间覆盖范围较大，使得每次assign能合并大量区间。在此假设下，区间总数期望维持在 $O(\log n)$ 级别。
节点设计与数据结构
import java.util.*;
/**
* 珂朵莉树（ODT）核心实现
* 重点：区间分裂、区间赋值、随机化均摊复杂度
*/
public class ChthollyTree {
/**
* 区间节点：表示一段值相同的连续区间 [left, right]
*/
static class Node implements Comparable<Node> {
long left; // 区间左端点（包含）
long right; // 区间右端点（包含）
long value; // 区间内的统一值
Node(long left, long right, long value) {
this.left = left;
this.right = right;
this.value = value;
}
/**
* 按左端点排序，用于TreeSet的排序依据
*/
@Override
public int compareTo(Node other) {
return Long.compare(this.left, other.left);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (!(obj instanceof Node)) return false;
Node other = (Node) obj;
return this.left == other.left;
}
@Override
public int hashCode() {
return Long.hashCode(left);
}
@Override
public String toString() {
return String.format("[%d, %d]=%d", left, right, value);
}
}
// 使用TreeSet维护按左端点排序的区间集合
private TreeSet<Node> intervals;
private Random random;
public ChthollyTree() {
this.intervals = new TreeSet<>();
this.random = new Random();
}
/**
* 从初始数组构建珂朵莉树
* @param arr 初始数组（下标从1开始）
*/
public ChthollyTree(long[] arr) {
this();
for (int i = 1; i <= arr.length; i++) {
intervals.add(new Node(i, i, arr[i - 1]));
}
// 合并相邻同值区间
mergeAdjacent();
}
核心操作：Split与Assign
split(pos) 是珂朵莉树的灵魂。它将包含pos的区间 $[L, R]$ 分裂为 $[L, pos-1]$ 和 $[pos, R]$ 两段，并返回指向 $[pos, R]$ 的迭代器。
/**
* 在位置pos处分裂区间
* 将包含pos的区间 [L, R] 分裂为 [L, pos-1] 和 [pos, R]
* @param pos 分裂位置
* @return 指向 [pos, R] 的节点（若pos超出范围则返回null）
*/
public Node split(long pos) {
// 查找第一个左端点 >= pos 的区间
Node it = intervals.ceiling(new Node(pos, pos, 0));
if (it != null && it.left == pos) {
// pos恰好是某个区间的左端点，无需分裂
return it;
}
// 查找pos所在的区间（左端点 < pos 的最大区间）
Node prev = intervals.lower(new Node(pos, pos, 0));
if (prev == null || prev.right < pos) {
return null; // pos不在任何区间内
}
long L = prev.left;
long R = prev.right;
long V = prev.value;
// 删除原区间，插入两个新区间
intervals.remove(prev);
intervals.add(new Node(L, pos - 1, V));
Node newNode = new Node(pos, R, V);
intervals.add(newNode);
return newNode;
}
/**
* 区间赋值：将 [left, right] 内所有值设为val
* 这是珂朵莉树效率的关键：合并区间降低复杂度
* @param left 左端点（包含）
* @param right 右端点（包含）
* @param val 新值
*/
public void assign(long left, long right, long val) {
// 先分裂边界，确保[left, right]精确对应若干完整区间
split(left);
Node endNode = split(right + 1);
// 获取 [left, right+1) 范围内的所有区间
Node from = intervals.ceiling(new Node(left, left, 0));
Node to = endNode != null ? endNode : intervals.last();
// 删除该范围内的所有区间
List<Node> toRemove = new ArrayList<>();
Node cur = from;
while (cur != null && cur.left <= right) {
toRemove.add(cur);
cur = intervals.higher(cur);
}
for (Node node : toRemove) {
intervals.remove(node);
}
// 插入合并后的单一区间
intervals.add(new Node(left, right, val));
}
区间查询操作
珂朵莉树天然支持各类区间查询，实现方式均为：先split边界，再遍历区间内所有节点。
/**
* 区间求和：计算 [left, right] 内所有元素的和
*/
public long rangeSum(long left, long right) {
split(left);
split(right + 1);
long sum = 0;
Node cur = intervals.ceiling(new Node(left, left, 0));
while (cur != null && cur.left <= right) {
long len = cur.right - cur.left + 1;
sum += len * cur.value;
cur = intervals.higher(cur);
}
return sum;
}
/**
* 区间最值：计算 [left, right] 内的最大值
*/
public long rangeMax(long left, long right) {
split(left);
split(right + 1);
long max = Long.MIN_VALUE;
Node cur = intervals.ceiling(new Node(left, left, 0));
while (cur != null && cur.left <= right) {
max = Math.max(max, cur.value);
cur = intervals.higher(cur);
}
return max;
}
/**
* 区间第k小：计算 [left, right] 内第k小的值
* 由于同一区间值相同，按值排序后累加计数
*/
public long rangeKth(long left, long right, long k) {
split(left);
split(right + 1);
// 收集区间内的所有(值, 长度)对
List<long[]> pairs = new ArrayList<>();
Node cur = intervals.ceiling(new Node(left, left, 0));
while (cur != null && cur.left <= right) {
pairs.add(new long[]{cur.value, cur.right - cur.left + 1});
cur = intervals.higher(cur);
}
// 按值排序
pairs.sort(Comparator.comparingLong(a -> a[0]));
long count = 0;
for (long[] p : pairs) {
count += p[1];
if (count >= k) {
return p[0];
}
}
return -1; // k超出范围
}
/**
* 区间幂次和：计算 [left, right] 内每个元素的x次方之和，再对mod取模
* 常用于题目要求 (a^1 + a^2 + ... + a^n) mod M 的场景
*/
public long rangePowerSum(long left, long right, int exp, long mod) {
split(left);
split(right + 1);
long sum = 0;
Node cur = intervals.ceiling(new Node(left, left, 0));
while (cur != null && cur.left <= right) {
long len = cur.right - cur.left + 1;
long pow = modPow(cur.value % mod, exp, mod);
sum = (sum + (len % mod) * pow) % mod;
cur = intervals.higher(cur);
}
return sum;
}
private long modPow(long base, int exp, long mod) {
long result = 1 % mod;
long b = ((base % mod) + mod) % mod;
int e = exp;
while (e > 0) {
if ((e & 1) == 1) {
result = (result * b) % mod;
}
b = (b * b) % mod;
e >>= 1;
}
return result;
}
辅助方法与工具函数
/**
* 合并相邻的同值区间（初始化后调用优化空间）
*/
private void mergeAdjacent() {
if (intervals.isEmpty()) return;
List<Node> merged = new ArrayList<>();
Node prev = intervals.first();
for (Node cur : intervals) {
if (cur == prev) continue;
if (prev.right + 1 == cur.left && prev.value == cur.value) {
prev = new Node(prev.left, cur.right, prev.value);
} else {
merged.add(prev);
prev = cur;
}
}
merged.add(prev);
intervals.clear();
intervals.addAll(merged);
}
/**
* 单点查询：获取位置pos的值
*/
public long get(long pos) {
Node it = intervals.floor(new Node(pos, pos, 0));
if (it != null && it.left <= pos && pos <= it.right) {
return it.value;
}
return 0; // 默认返回值
}
/**
* 单点修改：将位置pos的值设为val
*/
public void set(long pos, long val) {
split(pos);
split(pos + 1);
Node target = intervals.ceiling(new Node(pos, pos, 0));
if (target != null && target.left == pos && target.right == pos) {
intervals.remove(target);
intervals.add(new Node(pos, pos, val));
}
}
/**
* 打印当前所有区间（调试用）
*/
public void printIntervals() {
System.out.println("当前区间状态:");
for (Node node : intervals) {
System.out.println(" " + node);
}
System.out.println("区间总数: " + intervals.size());
}
完整测试与性能验证
/**
* 主程序：测试珂朵莉树各项功能
*/
public static void main(String[] args) {
// 测试1：基本功能验证
System.out.println("=== 测试1：基本操作 ===");
long[] arr1 = {1, 1, 2, 2, 2, 3, 3, 3, 3, 4};
ChthollyTree tree1 = new ChthollyTree(arr1);
tree1.printIntervals();
System.out.println("区间[3,7]和: " + tree1.rangeSum(3, 7));
System.out.println("区间[1,10]最大值: " + tree1.rangeMax(1, 10));
System.out.println("位置5的值: " + tree1.get(5));
tree1.assign(3, 6, 10);
System.out.println("赋值[3,6]=10后:");
tree1.printIntervals();
System.out.println("区间[1,10]和: " + tree1.rangeSum(1, 10));
// 测试2：区间第k小
System.out.println("\n=== 测试2：区间第k小 ===");
long[] arr2 = {5, 1, 3, 2, 4};
ChthollyTree tree2 = new ChthollyTree(arr2);
tree2.printIntervals();
System.out.println("[1,5]第1小: " + tree2.rangeKth(1, 5, 1));
System.out.println("[1,5]第3小: " + tree2.rangeKth(1, 5, 3));
System.out.println("[1,5]第5小: " + tree2.rangeKth(1, 5, 5));
// 测试3：大规模随机操作（性能测试）
System.out.println("\n=== 测试3：大规模随机操作 ===");
int n = 100000;
int m = 100000;
long[] arr3 = new long[n];
Random rand = new Random(42);
for (int i = 0; i < n; i++) {
arr3[i] = rand.nextInt(100) + 1;
}
ChthollyTree tree3 = new ChthollyTree(arr3);
long start = System.currentTimeMillis();
for (int i = 0; i < m; i++) {
int type = rand.nextInt(4);
long l = rand.nextInt(n) + 1;
long r = rand.nextInt(n) + 1;
if (l > r) { long t = l; l = r; r = t; }
switch (type) {
case 0:
tree3.assign(l, r, rand.nextInt(100) + 1);
break;
case 1:
tree3.rangeSum(l, r);
break;
case 2:
tree3.rangeMax(l, r);
break;
case 3:
long k = rand.nextInt((int)(r - l + 1)) + 1;
tree3.rangeKth(l, r, k);
break;
}
}
long end = System.currentTimeMillis();
System.out.println(m + "次随机操作耗时: " + (end - start) + "ms");
tree3.printIntervals();
}
}
复杂度分析
| 操作 | 最坏复杂度 | 随机数据期望复杂度 | 说明 |
|---|---|---|---|
| split | $O(\log n)$ | $O(\log n)$ | TreeSet操作 |
| assign | $O(n \log n)$ | $O(\log n)$ | 关键在于合并大量区间 |
| rangeSum/Max | $O(n \log n)$ | $O(\log n)$ | 依赖assign后的区间数量 |
| rangeKth | $O(n \log n)$ | $O(\log n)$ | 排序额外 $O(k \log k)$ |
| 空间 | $O(n)$ | $O(\log n)$ | 期望区间数 |
关键定理：若assign操作的区间端点是均匀随机的，则期望区间数量为 $O(\log n)$。
适用场景与局限性
适合使用珂朵莉树的场景：
1. 存在大量区间赋值操作，且赋值区间随机或覆盖范围广
2. 需要同时支持区间修改和多种区间查询
3. 数据具有时间戳或版本特征，天然适合区间分裂
不适合的场景：
1. 操作顺序精心构造以卡掉ODT（如反复单点修改）
2. 需要严格最坏复杂度保证的场合
3. 区间赋值极少、以单点修改为主的场景
总结
珂朵莉树是一种以优雅实现换取均摊效率的数据结构。它利用随机化假设，通过”区间分裂+合并”的核心思想，将复杂的区间操作简化为TreeSet上的集合操作。Java实现中，TreeSet 提供了自动排序和 $O(\log n)$ 的查找能力，与珂朵莉树的设计理念完美契合。虽然其最坏复杂度不理想，但在合适的场景下，它往往是最短代码、最快实现的选择。
