一句话：提出一种可连接、可分割的瞬态序列数据结构，兼具持久/临时结构并支持高效转换与索引、两端增删。
瞬态数据结构结合了临时数据结构、持久数据结构以及二者之间的快速转换。本文提出一种瞬态序列数据结构，支持在任意索引处高效读写，最坏情况时间复杂度为 O(K log_K n)；在两端进行 push 和 pop 的复杂度为 O(K log_K n)；分割与拼接的复杂度为 O(K log_K n + log_K^2 n)，其中 K 是用户定义的分块大小，n 是序列长度。作者给出详细分析，并指出在许多有利场景下，实际性能远好于这些悲观上界。文中还描述了具体实现，并提供一个合成基准来评估 push 和 pop 的性能。作者认为该结构有望成为通用的、一劳永逸的序列数据结构。
A transient data structure is a combination of an ephemeral data structure, a persistent data structure, and fast conversions between them. We present a transient sequence data structure that supports efficient read and write access at an arbitrary index with worst-case time complexity O ( K log K n ), pushing and popping at either end with complexity O ( K log K n ), and splitting and concatenation with complexity O ( K log K n +log K 2 n ), where K is a user-defined chunk size and n is the length of the sequence. We provide a detailed analysis of this data structure and show that, in many favorable scenarios, it performs much better than these pessimistic bounds might suggest. Furthermore, we describe its implementation, and provide a synthetic benchmark to evaluate the performance of push and pop . We believe that it is a good candidate for a one-size-fits-all, general-purpose sequence data structure.
@article{ChargueraudP26,
title = {A Catenable, Splittable, Transient Sequence Data Structure},
author = {Arthur Charguéraud and François Pottier},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {ICFP},
year = {2026},
doi = {10.1145/3828706}
}