这周打了一场模拟赛，学了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)\)，题解卡了卡常过了二分

线段树套单调栈2019-2020ICPCAsiaHongKongRegionalContestH.​​HoldtheLine​​题目大意你已经建造了一条由编号从到的战壕组成的防线，每条战壕最初都是空的。士

图论最短路次短路与k短路kruskal及应用树剖之重链剖分数据结构线段树浅析进阶可持久化优化建图平衡树BST和TreapFhq和Splay