哎，今天立了个flag，那就先学一个树套树吧。线段树套平衡树前置芝士：线段树、平衡树、二分答案顾名思义，线段树套平衡树是给线段树的每个节点都建一颗平衡树。我们先不考虑空间复杂度的问题。那么它一般用来解决什么问题呢？首先，线段树一般是用来维护序列的区间操作的，而平衡树一般

这周打了一场模拟赛，学了dsuontree，线段树合并，点分治边分治&点分树，树套树，K-DTree，STL中的bitset，分块&莫队学了好多东西。模拟赛中犯了低级错误文件怎么能写错啊啊啊啊，于是唱歌自省。在模拟赛中也学到了东西：线段树可以维护最短路，折半搜索签到题没签出来，看起来数组开不下但实际要用

树套树简介简单来说就是两个树形数据结构的嵌套，一般是值域套区间，或者区间套区间（二维区间）。P3380【模板】树套树看到查询排名与第\(k\)大会想到主席树，但其无法支持修改。所以考虑树套树，外层用棵线段树表示区间，内层用一棵权值线段树表示值域。考虑如何实现操作二，尝试二分，时

树套树还有很多东西要补...第\(k\)大值都树套树了，这里面就不写整体二分的离线做法LuoguP3242[HNOI2015]接水果形式化一下题意给定一棵\(N\)个点的树，现在树上有\(P\)条关键路径\(u_i\tov_i\)，同时每条路径有权值\(c_i\)有\(Q\)次询问，每次给出一条路

树套树这里主要介绍树状数组套权值线段树的方法，毕竟基本上所有的树套树题都能用这种方法解，并且时间复杂度都是\(n\times(logn)^2\)。思路这里有一道例题。【模板】树套树题目描述您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：查询\(k\)

笔者很菜，只会最简单的树状数组套权值线段树。不是，这玩意不就套娃吗，真ex啊题目简要：求\(x\)排名求排名为\(x\)的数求\(x\)前驱后继我们学了权值动态开点线段树就知道这些问题乱写就行了。但是套上\([l,r]\)区间呢，无修呢？我们会主席树这些乱写就行了。但是套上有

一道非常有意思的树套树。一眼一个空间\(n\logn\)时间\(n\log^{2}n\)的树套树，发现过不了。考虑优化。我们发现在中间线段树的地方可以不用平衡树存下来，只记最大值即可。然后我们对于每个横坐标开一颗fhq,然后分出\(\logn\)段区间，这些区间的最大值大于给定点的纵坐标。然后用

如何实现数据结构的嵌套？首先我们知道，单个数据结构是对一些存有某些信息的节点进行操作，从而达到目的。然后我们将这些节点换成另一种数据结构，更改的时候对某些数据结构进行修改，就可以实现嵌套。二维树状数组其实是最好写的一种树套树。单点修改，区间查询就像上文说的一样，我们

树套树树状数组，（动态开点线段树），平衡树二逼平衡树您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：查询\(k\)在区间内的排名查询区间内排名为\(k\)的值修改某一位值上的数值查询在区间内的前驱（前驱定义为小于，且最大的数）查询\(

线段树乱搞大法Part1普通线段树简单的区间或单点问题，支持四则运算（可以扩展成可合并的信息，如hash）权值线段树每个节点维护值域为\([l,r]\)的个数，可以维护全局第k大（线段树二分），zkw线段树...Part2懒标记区间操作，历史版本最值/和标记永久化区间操作，单点修改要求：操作顺序不

更好地观看总结今天是12月的第一天！美丽，晶莹的冬天！今天早上起来把昨天那道ULR#1】光伏元件给改了。这里说几点要注意的地方。建模网上都有，也比较典型，这里就不说了。就是这道题我先写了原始对偶，没过，然后写ssp，还是没有过。然后我开始怀疑人生了？后来我发现，对于上下界相等的边，就

数据结构待写vectorhash平衡树(splay,treap,AVL树)Link-Cut-Tree树套树不想写heap红黑树舞蹈链DLX主席树已写kdtree算法待写拓扑排序KMPmanacher树上启发式合并cdq分治不想写莫队已写逆元

\(\text{Link-LuoguBlog}\)原题传送门没啥重要的事情，就是终于过了这题非常开心，发现自己是莫队的时间戳部分写错了调了114514年我也只能说是十分趣味。以及今天深刻地认识到了带修莫队应该len=pow(n,0.66);。就是裸的带修莫队+值域分块，就不说了，直接放代码了昂。如果有人

1、CDQ分治与树套树CDQ分治本质是仍然是alogb和a+b的分治转化。2、整体二分与树套树整体二分可以看做是树套树上做dfs，或者树套树套树（矩阵第k大）上做dfs。3、树套树与主席树主席树更像是对于特定的可差分/可叠加问题，用前缀和差分/猫树分治的方式，解决这类问题，树套树则有着更

伪树套树CF19DPoints我们只关心最值而不是所有点的信息，所以不需要真的矩形查询对\(x\)建权值线段树，维护纵坐标最大值就能线段树二分求出询问矩形中最小的横坐标，再在这个横坐标上找最小纵坐标即可，可以在叶子上用set维护\(y\)实现。时间复杂度\(O(n\logn)\)

其实是我Li-Chao-Tree哒！！考虑转移\(f_x=\minf_{anc}+(d_{x}-d_{anc})p_x+q_x\)其中\(anc\)为\(x\)的祖先，然后满足\(d_{anc}\geqd_{x}-li_{x})\)。考虑如果用权值线段树+带撤销的李超树可以维护\(li_{x}\)可以维护\(li_{x}<0\)的情况。但是这个题

所谓树套树，其本质是通过用树维护一组树的根，从而维护强悍的数据1线段树套平衡树线段树套#include<bits/stdc++.h>usingnamespacestd;#defineMAXN50005intseg[MAXN<<2];intamin=1000000,amax=0;structNode{ intval,rnd,siz; intch[2]; }t[MAXN*80];intt

前言这是我个人使用的一些模板封装，限于个人能力，可能存在诸多不足与漏洞，在未加测试直接使用前请务必小心谨慎。更新可能会滞后于我本地的文档，如有疑问或者催更之类的可以在评论区留言。全文模板测试均基于以下版本信息，请留意版本兼容问题。Windows,64bitG++(ISOC++20)stack

Introduction树套树，顾名思义，就是将各类“树”据结构的节点换成“树”，以此解决一些问题。一般情况下，两层树分别维护区间信息和区间内权值的信息。而因为树套树极劣的空间复杂度和巨大的常数，经常需要使用动态开点和垃圾回收的方法降低空间复杂度，以及一定的卡常技巧（将较为短小

\(\color{purple}\text{Ⅰ.二维树状数组}\)\(\color{orange}\text{例一：P3372【模板】线段树1}\)$\color{green}\text{2023.1.1014:32}$回忆一下树状数组的区间修改

线套线规定使用OI坐标系。（按我的代码习惯）竖着关于\(1\simn\)建一棵线段树，该线段树的每个节点都是一棵内层线段树，若该节点的管辖区间为\([L,R]\)，则该内层线段树

题目大意：有一个\(n\timesn\)的矩阵，每个位置上初始值都为\(0\)，\(q\)次操作，分为两种：1.把横坐标在\([x_1,x_2]\)范围内，纵坐标在\([y_1,y_2]\)范围内的所有数加上一

查区间题目链接：YBT2023寒假Day7C题目大意给你一个序列，要你维护两种操作，区间取min和区间求第k小。思路关于区间求第k小，有一个方法，是树套树。外层线段树维护位

没事不要写LCT今天做了某题，大概需要维护个树链信息，题解区有以下几种做法\(n=8e4\)，时限\(2s\)二分+树剖+树套树(线段树套平衡树)，\(O(n\log^4n)\)，题解卡了卡常过了二分