程序设计竞赛ACM中树链剖分的研究

Research on Tree Chain Division in Programming Competition ACM

线段树在ACM大学生程序竞赛中应用非常广泛,是解决区间问题的一把利器,但对于树形数据结构线段树不能适用,考虑采用树链剖分进行操作。先从线段树的定义出发,讲述线段树的存储方式、建树、区间操作等原理及其实现,分析了线段树各个操作的时间复杂度并与其他算法进行对比。随后引出树链剖分使用重轻链分离的方法对线段树进行改进使之可以解决树上的操作问题;并以例题的方式介绍了树链剖分的应用。

Segment tree is widely used in ACM program competition.It is a powerful tool to solve interval problems.However,segment tree is not suitable for tree data structure.Starting from the definition of line segment tree,this paper describes the storage mode,tree construction,interval operation and other principles of line segment tree,and analyzes the time complexity of each operation of line segment tree and compares with other algorithms.Then,the tree chain division is introduced.The method of heavy and light chain separation is used to improve the line segment tree so that it can solve the operation problem of the tree.An example is given to introduce the application of tree chain subdivision.