树与区间结构

本页按场景选择方法；通过各条目链接阅读完整推演、源码和输出。

各段代码都是独立 main.go，Node 等同名类型不能合并。Go 1.22+，新建模块后一次只保存一个示例；本轮未执行。树必须有限且无环，旋转前要求对应孩子非 nil，DSU 下标须合法，线段树查询范围不得超出原输入长度；这些简例不统一进行输入校验。

要解决的问题	可选方法	选择前确认
逐层展示、复制结构或汇总子树	层序遍历、前序遍历、中序遍历、后序遍历	层序用队列；中序仅在二叉搜索树上给出有序序列，后序先处理孩子。
维护有序键，或理解搜索树退化	二叉搜索树与平衡树基础	普通搜索树最坏退化为 O(n)；旋转函数本身还不是完整 AVL 或红黑树。
沿字符串前缀组织检索	Trie 前缀树	耗时随单词长度增长；字符集很大时映射和指针的内存开销明显。
寻找祖先关系或树中最长路径	最近公共祖先或树的直径	公共祖先示例假设目标都在树中；直径按边数计，空树为零。
在线更新数值并查询区间聚合	树状数组或线段树	树状数组适合单点更新和前缀和；线段树示例提供区间和查询，更新需沿叶到根维护。
动态合并集合并判断连通	并查集	路径压缩与按秩合并加速查询；普通并查集不支持高效拆分集合。

按层、父子顺序访问树节点

层序遍历

正文、推演与完整示例：层序遍历。

队列先装入根节点，每取出一个节点就把它的孩子按顺序放到队尾。这样可以保证所有同层节点先于下一层被处理。 时间 O(n)。

若要按层分组，可以在每轮记录当前队列长度，再处理恰好这些节点。

前序遍历

正文、推演与完整示例：前序遍历。

递归实现清晰，但极深的树会增加调用栈；也可以用显式栈迭代。

中序遍历

正文、推演与完整示例：中序遍历。

普通二叉树并不具备这个有序性质，遍历顺序本身不会排序数据。

后序遍历

正文、推演与完整示例：后序遍历。

每个节点只访问一次，时间 O(n)，递归栈与树高度相关。

按键或字符串前缀建立索引

二叉搜索树

正文、推演与完整示例：二叉搜索树。

插入时从根比较，小值走左、大值走右，直到找到空位置。搜索和插入平均只经过树的高度，但有序输入可能把普通树退化成链表。 平均查找 O(log n)，退化时 O(n)。

需要稳定对数复杂度时，应使用 AVL、红黑树等平衡结构。

平衡树基础

正文、推演与完整示例：平衡树基础。

右旋把左孩子提升为局部根，原根变成它的右孩子；左旋操作对称。旋转保持所有节点的中序顺序，因而不会破坏搜索树性质。 AVL、红黑树还需在旋转之外维护平衡约束。

仅有旋转函数还不是完整平衡树，插入或删除后还需维护高度或颜色约束。

Trie 前缀树

正文、推演与完整示例：Trie 前缀树。

从根到节点的路径对应一个字符串前缀，相同前缀只存储一次。Insert 缺少边时创建新节点，Has 逐字符跟随边并检查结束标记。 插入和查询耗时与单词长度成正比。

它适合前缀检索；字符集很大时，节点中的映射和指针会带来明显内存开销。

汇总子树以求公共祖先与最长路径

最近公共祖先

正文、推演与完整示例：最近公共祖先。

递归函数在子树中找到目标节点就返回该节点；如果左右子树各返回一个目标，当前节点就是最近公共祖先。若只在一侧找到结果，就继续向上返回它。 普通二叉树中时间 O(n)。

这个简化实现假设两个目标都属于树，否则需要额外验证。

树的直径

正文、推演与完整示例：树的直径。

每个节点返回本子树的高度，同时用左高度加右高度更新穿过当前节点的路径长度。所有节点候选取最大值得到以边数计的直径，时间 O(n)。

一次后序遍历即可完成；空树直径为零。

维护可变数据的前缀和与区间和

树状数组

正文、推演与完整示例：树状数组。

索引 i 的最低有效位决定当前节点负责的区间长度。Add 沿相关节点向上更新，Prefix 沿区间分解向前累加，因此两者都只经过对数个节点。 单点更新与前缀查询均为 O(log n)。

本例树状数组对外下标从 0 开始，内部加一才转成树状数组索引。NewFenwick(n) 要求 n 非负，Add 的外部下标必须在 [0,n)；Add(-1, delta) 会让内部索引及最低有效位都为 0，循环无法前进，必须在调用前拒绝。Prefix(i) 包含 i 处元素，允许 i=-1 表示空前缀，但不能令 i≥n。它适合单点更新和前缀和；复杂区间操作通常需要线段树。

线段树

正文、推演与完整示例：线段树。

叶节点存放原数组，内部节点保存左右子区间之和。查询半开区间 [l,r) 时，从两侧向上移动并累加被完整覆盖的节点。 区间查询与单点更新为 O(log n)。

构建需要 O(n) 时间与空间；示例展示区间和，单点更新可沿叶到根路径同步修改。

合并集合并查询连通性

并查集

正文、推演与完整示例：并查集。

每个集合用一个代表根节点表示，Find 沿 parent 链寻找它。路径压缩缩短以后查询的路径，按秩合并避免树过高。 路径压缩与按秩合并使操作接近常数时间。

它擅长动态合并与连通性查询，但普通并查集不支持高效拆分已合并集合。

静态自检

NewFenwick(4) 后 Add(0,3)、Add(2,5)，预测 Prefix(1) 与 Prefix(2)。提示：Prefix 的终点包含在和中。

参考解法

分别为 3、8；树状数组对外下标从 0 开始，内部才加一。不要把 Prefix(2) 理解成半开区间 [0,2)。