珂朵莉树

前言

不知道你是否听说过一个叫珂朵莉树(ODT, Old Driver Tree)的”数据结构“，它有个名称：“老司机树”

珂朵莉这个人物名称来源于日漫《末日时在做什么？有没有空？可以来拯救吗？》中的女主角，之所以叫珂朵莉树是因为被发布在 codeforces 算法题背景人物中有珂朵莉

在洛谷的题目CF896C中文翻译中，不仅把题目背景介绍移除了，连背景图也移除了，真是本末倒置

wiki 上对它的解释如下

老司机树，ODT(Old Driver Tree)，又名珂朵莉树（Chtholly Tree)。起源自 CF896C。

会用 STL 的 set 就行。

把值相同的区间合并成一个结点保存在 set 里面。

这是一个基于 TreeMap 的暴力算法，用来解决一些区间赋值操作的数据结构题。在相对随机的数据场合，也堪堪能通过

几年前我刚在网络上偶然刷到相关的文章时，那时候我能找到的相关题解都还是基于 cpp 语言的，对 cpp 不熟悉成了我放弃理解这个算法的拦路虎

在现在大语言模型的帮助下，我重新理解了这个算法，并按自己的理解实现了 Java 版本和 Go 版本的 ODT

我的理解

先看题目要求

分别要求四个操作

1. 区间加
2. 区间赋值
3. 区间排序
4. 区间求和

我认为 ODT 树实现的核心就是，执行操作前，先按要执行的区间进行拆分

比如，区间 [left, right] 加操作，先以拆成以 left 起始的区间，再拆 right + 1 （以 right + 1为起始，就意味着必定有一个区间以 right 结尾）为起始的区间

拆完之后，就意味着在 [left, right] 这个大区间中，刚好会存在一个或者多个子区间在这个大区间内，而且这些子区间可以保证是大区间的子集

这样处理之后，只需要快速遍历这个大区间的所有子区间，就可以很方便地执行上面的四个操作

1. 对于操作1，每个子区间都加上给定的 val
2. 对于操作2，直接移除所有的子区间，并新增一个区间，范围就是 [left, right]，值为给定的值
3. 对于操作3，稍稍复杂一些，需要把所有子区间按 val 排序，然后找第 k 个值所在的区间
4. 对于操作4，同样是遍历整个子区间，使用快速幂计算模

对于查找子区间，由于 TreeMap 的特性，只需要
$$
O(log(n))
$$
的时间复杂度即可定位到起始区间

代码实现

public class ODT {

    private static final class TreeNode implements Comparable<TreeNode> {

        private final int left;

        private final int right;

        private long val;

        private TreeNode(int left, int right, long val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }

        private TreeNode(final int left) {
            this.left = left;
            this.right = Integer.MIN_VALUE;
        }

        @Override
        public int compareTo(final ODT.TreeNode o) {
            return Integer.compare(this.left, o.left);
        }

        @Override
        public boolean equals(final Object o) {
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            final TreeNode treeNode = (TreeNode) o;
            return left == treeNode.left && right == treeNode.right && val == treeNode.val;
        }

        @Override
        public int hashCode() {
            return Objects.hash(left, right, val);
        }
    }

    private final TreeSet<TreeNode> tree = new TreeSet<>();

    public ODT(long[] data) {
        Objects.requireNonNull(data, "input data is null");
        final int n = data.length;
        if (n == 0) {
            return;
        }
        var pre = 0;
        for (int i = 1; i < n; i++) {
            if (data[i] != data[i - 1]) {
                this.tree.add(new TreeNode(pre, i - 1, data[i - 1]));
                pre = i;
            }
        }
        this.tree.add(new TreeNode(pre, n - 1, data[n - 1]));
    }

    private void split(final int index) {
        final var floor = tree.floor(new TreeNode(index));
        if (floor == null || floor.left == index || floor.right < index) {
            return;
        }

        tree.remove(floor);
        tree.add(new TreeNode(floor.left, index - 1, floor.val));
        tree.add(new TreeNode(index, floor.right, floor.val));
    }

    public void add(final int left, final int right, final long val) {
        this.split(right + 1);
        this.split(left);

        tree.subSet(new TreeNode(left), new TreeNode(right + 1))
                .forEach(node -> node.val += val);
    }

    public void assign(final int left, final int right, final long val) {
        this.split(right + 1);
        this.split(left);

        tree.subSet(new TreeNode(left), new TreeNode(right + 1))
                .clear();
        tree.add(new TreeNode(left, right, val));
    }

    public long kth(final int left, final int right, final int k) {
        this.split(right + 1);
        this.split(left);

        final var treeNodes = tree.subSet(new TreeNode(left), new TreeNode(right + 1));
        final var sortTreeNodes = new ArrayList<TreeNode>(treeNodes.size());
        sortTreeNodes.addAll(treeNodes);
        sortTreeNodes.sort(Comparator.comparingLong(node -> node.val));
        var kth = k;
        for (final var sortTreeNode : sortTreeNodes) {
            final var length = sortTreeNode.right - sortTreeNode.left + 1;
            if (length >= kth) {
                return sortTreeNode.val;
            }
            kth -= length;
        }
        return -1;
    }

    public long powerSum(final int left, final int right, final long x, final long y) {
        this.split(right + 1);
        this.split(left);

        var ans = 0L;
        for (final var treeNode : tree.subSet(new TreeNode(left), new TreeNode(right + 1))) {
            final var length = treeNode.right - treeNode.left + 1;
            ans = (ans + this.pow(treeNode.val, x, y) * (length % y) % y) % y;
        }
        return ans;
    }

    private long pow(long base, long pow, final long mod) {
        var ans = 1L;
        base %= mod;
        while (pow > 0) {
            if ((pow & 1) == 1) {
                ans = (ans * base) % mod;
            }
            base = (base * base) % mod;
            pow >>= 1;
        }
        return ans;
    }

}

这里也有一份 Go 的实现，但 Go 的标准库中并没有 TreeMap 的实现，所以依赖了一个第三方库 gods，但 codeforces 不接受引入第三方库，以下代码提交后直接提示编译错误了，但实际应该是可行的实现（可以跑过给出的测试用例，虽然只有两个测试用例）

import (
  "fmt"
  "github.com/emirpasic/gods/trees/redblacktree"
  "slices"
)

type ODT struct {
  tree *redblacktree.Tree
}

type treeNode struct {
  left  int
  right int
  val   int64
}

func NewODT(data []int64) *ODT {
  tree := redblacktree.NewWith(func(a, b interface{}) int {
    treeNode1 := a.(*treeNode)
    treeNode2 := b.(*treeNode)
    return treeNode1.left - treeNode2.left
  })

  if len(data) == 0 {
    return &ODT{tree}
  }

  pre := 0
  n := len(data)
  for i := 1; i < n; i++ {
    if data[i] != data[i-1] {
      tree.Put(&treeNode{pre, i - 1, data[i-1]}, struct{}{})
      pre = i
    }
  }
  tree.Put(&treeNode{pre, n - 1, data[n-1]}, struct{}{})

  return &ODT{tree}
}

func (o *ODT) split(index int) {
  key, ok := o.tree.Floor(&treeNode{left: index})
  if !ok || key.Key.(*treeNode).left == index || key.Key.(*treeNode).right < index {
    return
  }

  node := key.Key.(*treeNode)
  o.tree.Remove(node)
  o.tree.Put(&treeNode{node.left, index - 1, node.val}, struct{}{})
  o.tree.Put(&treeNode{index, node.right, node.val}, struct{}{})
}

func (o *ODT) foreach(start, end int, handle func(*treeNode)) {
  cur, _ := o.tree.Floor(&treeNode{left: start})
  iterator := o.tree.IteratorAt(cur)
  for {
    node := iterator.Key().(*treeNode)
    if node.left > end {
      break
    }
    handle(node)
    if !iterator.Next() {
      break
    }
  }
}

func (o *ODT) Add(left, right int, val int64) {
  o.split(right + 1)
  o.split(left)

  o.foreach(left, right, func(node *treeNode) {
    node.val += val
  })
}

func (o *ODT) Assign(left, right int, val int64) {
  o.split(right + 1)
  o.split(left)

  var deleteNodes []*treeNode
  o.foreach(left, right, func(node *treeNode) {
    deleteNodes = append(deleteNodes, node)
  })

  for _, node := range deleteNodes {
    o.tree.Remove(node)
  }

  o.tree.Put(&treeNode{left, right, val}, struct{}{})
}

func (o *ODT) Kth(left, right, kth int) int64 {
  o.split(right + 1)
  o.split(left)

  var sortNodes []*treeNode
  o.foreach(left, right, func(node *treeNode) {
    sortNodes = append(sortNodes, node)
  })

  slices.SortFunc(sortNodes, func(a, b *treeNode) int {
    return int(a.val - b.val)
  })

  for _, node := range sortNodes {
    length := node.right - node.left + 1
    if kth <= length {
      return node.val
    }
    kth -= length
  }
  return -1
}

func (o *ODT) PowerSum(left, right int, x, y int64) int64 {
  o.split(right + 1)
  o.split(left)

  ans := int64(0)
  o.foreach(left, right, func(node *treeNode) {
    ans = (ans + ((int64(node.right-node.left+1)%y)*pow(node.val, x, y))%y) % y
  })
  return ans
}

func pow(base, pow, mod int64) int64 {
  ans := int64(1)
  base %= mod
  for pow > 0 {
    if (pow & 1) == 1 {
      ans = (ans * base) % mod
    }
    base = (base * base) % mod
    pow >>= 1
  }
  return ans
}

总结

ODT 树不算是一个多高级的数据结构，甚至也不算一个数据结构，强依赖了 TreeMap

我之所以有想法去探讨这个算法，应该是因为我们都喜欢珂朵莉吧