一.neko_tree
猫neko树是一种维护序列的数据结构。在处理绝大多数线段树能处理的问题（如最大子段和，区间最大值，区间\(gcd\)等满足结合律且能快速合并的信息）上能做到\(O(nlogn)\)预处理后\(O(1)\)的询问。但是不支持修改。
neko树怎么维护信息？想象在线段树上取得区间\([l,r]\)间的信息，每次都会取\(mid\)，在\(log\)层递归中，\(l,r\)一定会被\(mid\)分开一次。所以，neko其实就是维护每一层\((dep)\)上每一个可能成为\(mid\)的点，即线段树当前层数每一个区间的中点，到这个区间两端的信息。维护\(f[i][j]\)存第\(i\)层上序列第\(j\)位到它所在区间\(mid\)的信息。对于每次询问的两点，找到\(mid\)，合并返回\(mid\)两端的信息即可。
但是怎么找\(mid\)也是一个问题。如果我们把这两个点放到一棵满线段树上，不难发现把它们分开的那个点其实是它们\(lca\)的\(mid\)。如果把这两个点的编号转化为二进制，\(mid\)就是从第一位开始第一个不一样的数位的前一个数位。可以直接
lg[pos[l]]-lg[pos[l]^pos[r]]
neko树有点线段树+ST表的意味。但因为不支持修改，纯数据结构题一般做不了。不过neko也有自己发挥的空间。
EG1 优化dp
比线段树快，比线段树好写
EG2 区间凸包
给定平面上的一些点，保证横坐标单调递增，每次给定\(l,r\)，求这个区间内点的凸包的面积。
一个点的影响是难以确定的，所以必须求出凸包。正常情况下可以写线段树套可持久化平衡树。在线段树结点上保存\([l,r]\)上的凸包，用可持久化线段树合并来保证复杂度。预处理\(O(nlog^2n)\)，单次询问\(O(log^2n)\)。考试时 不会有人写这种鬼东西的 多半写不出来。
思考使用neko树的做法。只要我们可持久化地保存\(prel,prer\)为区间的凸包，就只需要资磁对左右两边预处理的凸包二分出一个公切线，然后进行计算即可，并不需要直接合并两个平衡树维护的凸包。而这里的凸包只有单调的插入，用简单的可持久化数组就可以直接维护，阳间一些。而且预处理复杂度相同，单次询问只有\(O(logn)\)
二.一道运用了neko_tree分治的题
法一 SAM+分块
首先先对所有串建一个广义SAM，然后把询问按\(r\)为第一关键字，\(l\)为第二关键字排序，对于每次\(r\)的加一，只有可能是包含串\(r\)在SAM上的结点产生贡献。提前开一个\(vector\)记录每一个串出现的位置，然后暴力跳\(link\)。对于每一个结点，我们都维护当前（包含\(r\)）的最长连续段。更新时，如果结点\(i\)先前最大结点恰为\(r-1\)，那么直接\(right[i]=r\)，否则重新开始计数\(left[i]=right[i]=r\)。对于一个询问\([li,ri]\)，如果当前节点的\(le\)小于\(li\)，则可以产生贡献。根据广义SAM的定理，暴力跳的次数最多为\(len \sqrt{len}\)。（时间，空间得到保证） ，且现在的问题就是需要一种数据结构，支持\(O(1)\)修改以及较快的查询区间最大值。所以用分块来维护。时间复杂度\(O(len\sqrt{len}+m\sqrt{n})\)。
但是因为出题人是逆天，这种做法被卡了。
法二 SAM+neko树分治
求多个串的\(maxlcp\)还有除了广义SAM外的另一种方法。我们对其中一个串建一个SAM，然后把所有串依次放到上面匹配。记\(f[i][j]\)表示第\(i\)个串的以第\(j\)位为结尾的最长的匹配。那么要求\(maxlcp\)就是把每个\(f[i][j]\)算出来，先求\(p[j]=MIN_{i=1}^{len}(f[i][j])\)，再求\(MAX(p)\)即为答案。
于是在这道题里我们用这种方法。我们求“在当前情况下，能被更新的答案有哪些”。对他使用neko树分治吧。求前缀和后缀的\(f\)，仿照整体二分对询问和位置同时分治。当在区间\([l,r]\)时，我们处理这个区间内的询问，如果过\(mid\)，那就取\(f\)两点的\(min\)，再套上一个\(max\)。如果不过，就继续分治（neko树分治的核心思想）。
看起来似乎做完了，但上述做法的复杂度其实是有问题的，当故意构造\(mid\)位置串的长度极长时复杂度会退化。所以需要一个新的trick，倍增分治。为了选出的\(mid\)尽可能小，我们设定阈值\(x\)，如果存在\(len\le 2^x\)的串，就选择这些串的中间位置作为\(mid\)，否则就\(x++\)直到可以为止。
这样做的复杂度是多少呢？
单次(一个x)每个串会被遍历\(O(\log n)\)次,总共有\(\log len\)个x.所以总共每个串会被遍历\(O(\log n\log len)\)。
首先,分治预处理(求mid为中心的前后缀)的复杂度为\(O(lenlognloglen)\)。然后,设区间内跨\(mid\)的询问数有\(m\)个。如果\(|S|\le \frac{len}{\sqrt{m}}\)，那么扫描的复杂度即为\(O(len\sqrt{m})\)。否则区间长度\(k\le \sqrt{m}\)，且区间个数为\(k^2\)。经过记忆化，总时间复杂度为\(O(k^2*\frac{len}{k}\le len\sqrt{m})\)。
另外，为了省下赋值和清空的时间，必须直接开很大一块内存池，并且支持\(O(1)\)的清空。指针是很好的选择。RT
int ncc[L<<1],*poi=ncc;
I void newblock(int l,int r,int nd) { //nd即为需要的空间
poi=ncc;
for(int i=l;i<=r;++i) f[i]=poi,poi+=nd+2;
}
综上所述，总时间复杂度为\(O(m\log m+len(\log n\log len+\sqrt{m}))\)
(其实也就是少了不到三的常数)
简单の总结
neko树不是很强的数据结构，在实际中绝大多数作为 优化\(dp\)/维护不带修数值/卡常 的工具使用。它的意义是好写+常数极小，用在特殊情况下替代线段树。偶尔会有非它不可的题，但难度都会很高。