前言许多算法的本质是统计。线段树用于统计，是沟通原数组与前缀和的桥梁。《统计的力量》清华大学-张昆玮关于线段树前置知识：线段树OIWiki。线段树是一种专门维护区间问题的数据结构。线段树对信息进行二进制化处理并在树形结构上维护，以此让处理速度达到\(O(\log{n})\)

前言许多算法的本质是统计。线段树用于统计，是沟通原数组与前缀和的桥梁。《统计的力量》清华大学-张昆玮关于线段树前置知识：线段树OIWiki。线段树是一种专门维护区间问题的数据结构。线段树对信息进行二进制化处理并在树形结构上维护，以此让处理速度达到\(O(\log{n})\)

一、简介zkw线段树专门用于线段树卡常，同时码量比普通线段树要小。原理是通过将线段树补成完全二叉树，直接找到第\(i\)个叶子节点（编号为\(p+i\)），然后从下往上更新，从而避免递归。这里常数p=1<<(__lg(n)+1)，编号为\(p\)和\(p+n+1\)的叶子为虚点，编号为\(p+1\simp+n\)的

事情的起因是我某天吃晚饭时打算找个电子榨菜，然后b站搜索线段树，看到了一个名叫zkw线段树（即非递归线段树），由于不是面向Oier的，所以饭后我又找了几个博客看，现在写下心得记录（其实只是不想在书签留3个位置给线段树）为什么要学习非递归线段树，这个问题大部分博客解释为普通线段树

介绍非递归线段树实现方法，码量较短。zkw线段树的构造原理：普通线段树采用堆存储，zkw线段树本质上是满二叉树（若没有该区间则为空点）但根据实际情况，原区间不一定构成满二叉树，据查询方式限制，空间开到最接近的\(2^n\)（据性质树值域=底层节点数），即不存在的点有虚点填充。既然不