ToB企服应用市场:ToB评测及商务社交产业平台

标题: zkw 线段树-原理及其扩展 [打印本页]

作者: 张裕 时间: 2024-11-15 08:50
标题: zkw 线段树-原理及其扩展
前言

许多算法的本质是统计。线段树用于统计，是沟通原数组与前缀和的桥梁。
《统计的力量》清华大学-张昆玮

关于线段树

前置知识：线段树 OIWiki。
线段树是一种专门维护区间题目的数据结构。
线段树对信息进行二进制化处置处罚并在树形结构上维护，以此让处置处罚速度达到 \(O(\log{n})\) 级别。
线段树的实现方式

由于线段树的树形结构特点，每次修改查询可以从根节点向下二分查找需要用到的节点，因此较为普遍且快捷的线段树会使用递归实现。
但递归实现的线段树由于每次要从根节点递归向下传递子树信息，导致常数较大，容易被卡常，所以出现了常数更小的递推实现的线段树（膜拜 zkw 大佬）。
zkw 线段树

先来讲一些小原理。
一、原理

由于递归实现的线段树不是一棵满二叉树，其叶子节点位置不确定，导致每次操作都需要从根节点开始自上而下递归依次寻找叶子节点，回溯时进行维护，递归过程常数就比较大了。
所以 zkw 线段树就直接建出一棵满二叉树，原序列信息都维护在最底层。严酷规定父子节点关系，同层节点的子树巨细相等。
这样每个叶子节点都可以直接找到并修改，由于二叉树父子节点的二进制关系，就可以递推直接找到对应节点的父亲节点自下而上地维护节点关系。
二、初始化

1、建树

对长度为 \(n\) 的序列建一棵 zkw 线段树，其至少有 \(n+2\) 个叶子节点。其中有 2 个用来帮助维护区间信息的虚点，有 \(n\) 个用来存原序列信息的节点。
如图（【模板】线段树 1的样例为例，下同）：

建树时先求出虚点 \(P\) 位置，然后直接向其他叶子节点读入信息即可:
[code]//先求虚点 P P = 1; while(P

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)