线段

# 线段树专题 注意：此文乃个人对线段树的见解，各位大佬如发现错误请批评指正 > 什么是线段树 线段树顾名思义，就是将一个数列的各个区间当成是树上的节点并维护。 > 线段树用来干什么 一般用来进行区间查改(矩阵查改本蒟蒻不会) > 线段树节点如何编号 假设当前节点的编号为 $k$，左儿子的编号为 $ ......

视频链接： Luogu P1803 凌乱的yyy / 线段覆盖 #include <iostream> #include <cstring> #include <algorithm> using namespace std; struct line{ int l,r; //线段的左,右端点 bool ......

# 建树： ```cpp int a[100005],d[100005]; void build(int s,int e,int p){// 建树 // 对区间[s,t]建立线段树，当前根编号为p if(s==e){ d[p]=a[s]; return ; } int m=s+((e-s)>>1); ......

描述 给定n个数据，有两个操作，加减其中的一个数据，当然还可查询在某段数据的和。 输入 输入数据有多组，每组数据的第一行输入n，1=<n<=500000,代表数据的个数。第二行输入具体数据，数据为正整数，范围在1到10000.第三行输入m，1<=m<=100000,表示操作的次数。包含了修改和查询操 ......

# [P3372【模板】线段树 1](https://www.luogu.com.cn/problem/P3372) 参考代码 ```cpp #include #define LC (cur*2) #define RC (cur*2+1) typedef long long LL; const in ......

## [$T125847$ 【模板】动态开点线段树](https://www.luogu.com.cn/problem/T125847) ### 题目背景 **注意：请注意时间限制是800ms 请使用较快的输入输出** **注意：空间限制是128MB 请不要开long long** **时限在std ......

给 $n$ 个数 $a_1, a_2, \cdots, a_n$ 。 支持 $q$ 个操作： 1. 1 x d ，修改 $a_x = d$ 。 2. 2 l r ，查询 $min_{i = l}^{r} a_i$ ，并输出 $\sum_{i = l}^{r} [a_i = min_{i = l}^{ ......

给 $n$ 个数 $a_1, a_2, \cdots, a_n$ 。 支持 $q$ 个操作： 1. 1 x d ，修改 $a_x = d$ 。 2. 2 l r ，查询 $[l, r]$ 中的最大子段和。 一：确定需要维护的信息。根据分治中线讨论，哪些信息可以合并出所需信息。递归讨论新信息如何合并。 ......

给 $n$ 个数 $a_1, a_2, \cdots, a_n$ 。 支持 $q$ 个操作： 1. 1 l r d ，令所有的 $a_i(l \leq i \leq r)$ 加上 $d$ 。 2. 2 l r ，查询 $max_{i = l}^{r} a_i$ 。 区间修改的线段树要比基础线段树多考 ......

给 $n$ 个数 $a_1, a_2, \cdots, a_n$ 。 支持 $q$ 个操作： 1. 1 l r d ，令所有的 $a_i(l \leq i \leq r)$ 加上 $d$ 。 2. 2 l r d ，令所有的 $a_i(l \leq i \leq r)$ 乘上 $d$ 。 3. 3 ......

## [【模板】线段树 2](https://www.luogu.com.cn/problem/P3373) 如题，已知一个数列，你需要进行下面三种操作： - 将某区间每一个数乘上 $x$； - 将某区间每一个数加上 $x$； - 求出某区间每一个数的和。 #### 输入格式 第一行包含三个整数 $ ......

## 下饭写错合集： - `if(l>R||r=R||r>1) #define ls(x) (x #define ll long long #define mid ((l+r)>>1) #define ls(x) (xR||r=L&&r #define mid ((l+r)>>1) #define ......

以前一直以为是什么高深的东西，然后学会了才发现没那么难。 ## 超级源点 假设我现在有： ```mermaid graph TD 1 2 3 ``` ```mermaid graph TD 4 5 6 ``` 需要给1连上4，5，6；2连上4，5，6；3连上4，5，6。它们的边权为1。 那你会说，这 ......

给出一个长度为n的数列A同时定义一个辅助数组 B，B开始与 A完全相同。接下来进行了m次操作，构造一个数据结构维护以下五类操作： 1. 对于所有i$\in$[l,r],将$A_i$加上k 2. 对于所有i$\in$[l,r],将$A_i$min($A_i$,v) 3. 求$\sum\limits_{ ......

[传送门](https://www.luogu.com.cn/problem/P5787) 分析： $1$、**并查集判断二分图：** 定义$2n$个点，染成黑白两色，代表两个不同的集合，$a_1$与$a_{1+n}$为不同的颜色，以此类推，对于$a_i$和$a_j$的连边，判断$a_i$和$a_j ......

[例题传送门：Count on a tree](https://www.luogu.com.cn/problem/P2633) 简要题意：有棵$n$个节点的树，每次点有个权值$a_i$，每次询问给出$u,v,k$，求$u,v$两个节点的简单路径上(包括$u,v$)上第$k$小的点，保证数据有解，强制 ......

[传送门](https://www.luogu.com.cn/problem/P2824) 很巧妙的一个题 直接排序肯定会$T$飞 我们发现问题只有一个：第$q$个位置上的数字 不难想到从这里入手，二分答案，考虑第$q$个位置上的数字是什么，不妨设他为$x$ 然后把大于等于$x$的数变成$1$，小于 ......

线段树一般用于维护符合结合律的信息。可以用于求区间最大值 区间和 区间最小值 最大子段和甚至于最大负数最小正数之类的信息。事实上线段树只有你想不到，很少有做不到的，算是相当常用的数据结构。 下面将结合个人理解和具体题目来讲一讲线段树。 [https://www.luogu.com.cn/proble ......

# 【主席树】洛谷 P3834 可持久化线段树2 题目链接：https://www.luogu.com.cn/problem/P3834 主席树是可持久化线段树的一种，也叫做可持久化权值线段树，主要可以用来O(logn)求静态区间的第k小数。 总所周知，普通线段树每次修改会遍历logn个点，那么我们 ......

关于可刺激化修道士表舅已经黑。 因为傻逼 lxd 告诉我我的表舅已经黑写法是错误的，所以稀里糊涂的让他改成了他的那种写法。但是我的也是对的。 比如区间加和区间查和，维护一个 $tag$，表示表舅的值。然后在区间加的时候，经过的区间的 $sum$ 的值可以直接加，但是只有在 ```cpp if (x ......

线段树 vs 树状数组 1. 代码长度： 树状数组段 2. 可扩展性：线段树强， 二树状数组仅局限于和的处理 3. 思维难度：线段树简单 比如 区查区改 树状数组还要打开多项式搞 延迟标记：为了处理当修改区间是$[1,n]$时所有节点都要被修改一遍的情况 如果修改区间覆盖当前区间，那么这颗子树之内所 ......

# 线段树 ```c++ struct Node{ int l, r, sum, lazy; }tr[N * 4]; int a[N]; void pushup(int u) { tr[u].sum = tr[u > 1; pushdown(u); build(u = l && tr[u].r > ......

点到线段最短距离的运算与点到直线的最短距离的运算二者之间存在一定的差别，即求点到线段最短距离时需要考虑参考点在沿线段方向的投影点是否在线段上，若在线段上才可采用点到直线距离公式。 通俗的说，我们按照求点到直线的距离作垂线后，交点不一定在线段上。 如图 $1$ 所示。 ![image](https:/ ......

事先声明：本文并非线段树教学。只是一些理解Trick。若您需从0学起线段树建议您移步其他博文呢qwq 感谢 Idea 提供 [尺子姐姐的博客！](https://www.cnblogs.com/ruierqwq/)，尺子好闪，拜谢尺子！ 我们在学习线段树的时候，对于乘法“lazy tag 先乘再加” ......

## 多信息合并 $\text{GSS3 Solution}$ [$\text{link}$](https://www.luogu.com.cn/problem/SP1716) 对于线段树的每个结点，记录其区间和（$sum$），区间前后缀最大子段和（$lmax,rmax$）和区间最大子段和（$vma ......

**优化建图** ~~发现并没有人写得很详细的样子，那我也摆烂好惹~~ 点击查看目录 [TOC] ## 前言 >众所周知，连边的时间复杂度一般是 $O(1)$，但，当连边的对象是一个连续的树上区间的时候，我们或许有更优的连边方式：优化建图。 前置知识： * 树链剖分 * 线段树 * 树上倍增 * D ......

线段树是用于在区间上进行信息统计的二叉树。 ## 线段树的性质 1. 每个节点都代表一个区间。 1. 有唯一的根节点，代表整体区间 1. 每个夜间点代表长度为 $1$ 的单位区间 1. 出叶节点和根节点之外的内部节点 $[l,r]$，取 $mid=\lfloor\frac{1+r}{2}\rfloo ......

## 历史值问题 历史值：在维护序列 $A$ 的同时，在每次操作后，序列 $A$ 会对序列 $B$ 的对应位置产生贡献。 - 历史版本和：每次操作后，$B_i \leftarrow B_i + A_i$。 - 历史最大值：每次操作后，$B_i =\max(B_i,A_i)$。 ### 历史版本和： ......

# $$\texttt{线段树}$$ [OI-wiki Link](https://oi-wiki.org/ds/seg/) 线段树是一种用于维护区间信息的数据结构，可以在 $O(\log n)$ 的复杂度下求出一个大小为 $n$ 的数组的区间信息（如区间和、区间最大值等），也可以在同样时间复杂度下 ......

#### 题意： 给你一个长为 $n$ 的序列 $a$，支持： - `1 l r x`：$\forall a_i \in [l,r],a_i \gets \min(a_i,x)$。 - `2 l r`：求 $\sum_{i\in [l,r]} a_i$。 - `3 l r`：求 $\max_{i \ ......