数据结构——猫树学习笔记喵~使用情景没有修改，只有区间查询；且维护的信息可以快速合并且满足结合律。我们直接抛出猫树的复杂度：预处理\(\mathcalO(n\logn)\)，查询\(\mathcalO(1)\)如果询问的操作是可重复贡献问题（RMQ），那么她和ST表是理论复杂度相同的。如果询问的操

猫树是线段树的一个特殊版本，猫树不再支持修改操作，类似\(\text{ST}\)表猫树支持高速区间查询，每次查询都只需要进行\(1\)次合并操作，设单次合并操作的复杂度为\(O(k)\)，建立猫树的复杂度是\(O(kn\logn)\)的，而查询的复杂度是\(O(k)\)的一般单次查询的复杂度是\(O(1)\)，所

就是说，对于分治区间\([l,r]\)，记\(mid=\lfloor\dfrac{l+r}{2}\rfloor\)，对于\([l,mid]\)和\([mid+1,r]\)内的询问继续递归，把跨越两边的询问用左右的信息合并处理。P6240好吃的题目物品\(i\)有体积\(w_i\)和价值\(c_i\)，多次询问，对\([l,r]\)做01背包，问体积\(\let

就是说，对于分治区间\([l,r]\)，记\(mid=\lfloor\dfrac{l+r}{2}\rfloor\)，对于\([l,mid]\)和\([mid+1,r]\)内的询问继续递归，把跨越两边的询问用左右的信息合并处理。P6240好吃的题目物品\(i\)有体积\(w_i\)和价值\(c_i\)，多次询问，对\([l,r]\)做01背包，问体积\(\let