| 数据结构名称 | 时间复杂度（一般）（建立—修改—查询） | 时间复杂度（合并） | 时间复杂度（分裂） | 时间复杂度（分治） |
|---|---|---|---|---|
| 数组 | \(\mathcal{O}(1)-\mathcal{O}(1)-\mathcal{O}(1)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n)\) |
| 可持久化数组 | \(\mathcal{O}(1)-\mathcal{O}(\log n)-\mathcal{O}(\log n)\) | \(/\) | \(/\) | \(\mathcal{O}(n)\) |
| \(\rm Hash\) 表 | \(\mathcal{O}(1)-\mathcal{O}(1)-\mathcal{O}(1)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n)\) |
| 可持久化 \(\rm Hash\) 表 | \(\mathcal{O}(1)-\mathcal{O}(\log n)-\mathcal{O}(\log n)\) | \(/\) | \(/\) | \(\mathcal{O}(n)\) |
咕咕咕。。。
原文：https://www.cnblogs.com/hhoppitree/p/14961917.html