数据结构中的静态手指定理

静态手指定理：令f被视为一个称为手指的特定元素。

那么下面的表达式限制了序列播放的代价

O(m + n log(n) + Σ Sum log (|f - i[j]| + 1))j

注意：| fi | 表示为手指与物品i之间物品对称排列的距离。

其中m表示在最多具有n个节点的树上的更新或访问操作数。

观察到，至少在摊销意义上，对一棵树进行前m次操作所花费的时间永远不会超过n个节点，这与平衡二叉搜索树（如AVL树，2-3个树等）所花费的时间相似。