Articles under the label of 树链剖分

树链剖分学习笔记

树链剖分是一种树路径信息维护算法。把整棵树划分成许多条链，使每个节点都在唯一的链上，对每一条链维护一棵线段树，把在树上的操作转移到线段树上。ž将一棵树划分成若干条链，用数据结构去维护每条链，保证每个点在且仅在一条链上，通过数据结构维护这些链的信息，复杂度为$ O(logN) $