[OI] 猫树

概述

猫树是一种与线段树类似的数据结构

线段树在解决不带修区间问题时，对于单次查询是 的，此时运用猫树就可以将单次查询的复杂度降到

合理运用分块的思想，在区间内分块，思考我们在块上查询的过程

设黑色的线段为整个区间，红色的线段为查询区间，黑色线段中间的凸起为中点

既然我们能在线段树上做，那么该问题一定具有区间可合并性

那么我们可以预处理出中点前的节点到中点的区间信息（后缀和）和中点后的节点到中点的区间信息（前缀和），这样就可以快速求解跨中点的查询

比如，假设查询 ，则有 ，因此我们可以快速求出答案

然而到这里我们并没有办法求解不跨中点的查询，因此我们就需要结合线段树了

尝试对区间建立一颗线段树，然后在线段树每个节点上都建立这样一个前缀+后缀的组合，这样，在遇到不跨中点的查询的时候，直接转到下一层，直到这个查询变成跨中点的查询为止

猫树的好处是，最多只会进行一次合并操作，在合并复杂度较高的维护信息中可能会比较好用

例题（待完善）

[SPOJ GSS1] Can you answer these queries I

对若干询问区间求区间内最大子段和（）

[P6240] 好吃的题目

区间 01 背包

看到一个很抽象的公式

相关知识

[OI] 猫树
OI
「猫树」猫树公司黄页
DIY猫树，简易猫爬架，简易猫树，猫树。#造型猫树 #简易猫
【猫树】
猫树
树猫
猫树的由来
壁挂猫树
猫树详解

原文链接: [OI] 猫树 https://www.mcbbbk.com/newsview1186630.html