线段

# dfs序线段树 [1.树上操作](https://www.ybtoj.com.cn/contest/541/problem/6) ### 思路 遍历一整棵树，记录一下节点 $u$ 的所对应的子树的节点数 $siz_u$ 以及 $dfs$ 序 $dfn_u$ 根据整棵树的 $dfs$ 序，我们可以 ......

## 2023HDU多校9__Capoo on tree（二分+树链剖分+可持久化线段树） ### [题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=7371) ### Solution $Hint1$ 考虑如何进行对某一相同点权的所有点进行点权$+1 ......

P4246 首先注意到两个点应该怎么联通，有可能直接走进去对吧，也有可能是绕一圈走过去，我们考虑整个在求连通性的时候最重要的是哪些点，是左上角，左下角，右上角和右下角，所以我们考虑维护他们之间的连通性。 然后连通性很好合并，所以我我们可以把这个东西搬上线段树维护一大段区间的四个角互相是否可达。 然后 ......

- # **线段树 $1.0$** 线段树 $1.0$ 可以实现对区间内的数加减，查询区间和的操作。 ## **例题** [【模板】线段树 1](https://www.luogu.com.cn/problem/P3372) ## **原理** ### **定义** `l,r` ：分别表示节点表示的 ......

# 前置知识 动态开点权值线段树 相信各位都会 # 线段树合并 我们考虑对于两棵权值线段树，由于动态开点的缘故，这两棵树都是不满的 我们考虑能不能把这两棵树所保存的信息合并在一起 我们考虑这么一件事就是说，由于树不满，我们可以暴力扫 分为三种情况(设把 $b$ 所在树并到 $a$ 内，$a$ 和 $ ......

调了整整5个小时,结果发现自己建树的方式有误,气死我了气死我了,比较好的一道线段树(虽然我不会 #include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m,res,point; vector<int>v[2]; / ......

描述 线段相交有两种情形：一种是“规范相交”，另一种是“非规范相交”。规范相交是指两条线段恰有唯一一个不是端点的公共点。即如果一条线段的端点在另一条线段上则不视为相交。如果两条线段有部分重合，也不视为相交。而非规范相交则把以上两种情况都视为相交。如下图所示： 规范相交认为a，b两种情况都是不相交的， ......

**3348: 线段相交Ⅲ** 时间限制(普通/Java):1000MS/3000MS 内存限制:64000KByte **描述** >线段相交有两种情形：一种是“规范相交”，另一种是“非规范相交”。规范相交是指两条线段恰有唯一一个不是端点的公共点。即如果一条线段的端点在另一条线段上则不视为相交。如 ......

我视界里最不珂爱的 SGT 代码我是真的自己写不动 所以这个是照着校 O勾 填空题目写的符合自己习惯的代码 我们要动态维护平面里的直线和诸如 $x=t$ 这类直线的信息 大概原理不难理解 就是权值线段树对应区间维护的是当前区间的最优解 最优解指的是在这个区间里面最上面的线段 可以完全碾压别的线段那一 ......

就是个解方程。 #include <bits/stdc++.h> #define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; double ansx, ansy; bool pingxing(do ......

描述 线段相交有两种情形：一种是“规范相交”，另一种是“非规范相交”。规范相交是指两条线段恰有唯一一个不是端点的公共点。即如果一条线段的端点在另一条线段上则不视为相交。如果两条线段有部分重合，也不视为相交。而非规范相交则把以上两种情况都视为相交。如下图所示： 规范相交认为a，b两种情况都是不相交的， ......

在建图连边的过程中，我们时常会碰到这种题目，一个点向一段连续的区间中的点连边或者一个连续的区间向一个点连边，如果我们真的一条一条连过去，那一旦点的数量多了复杂度就爆炸了，这里就需要用线段树的区间性质来优化我们的建图了。 那棵线段树大概长这个样子。 ![线段树](https://images.cnbl ......

# 线段树 线段树是一种二叉树形数据结构，用于解决区间查询和区间修改问题。它将一个数组划分为若干个连续的区间，每个区间对应线段树的一个节点。通过递归地构建线段树，我们可以在O(log n)的时间复杂度内完成区间查询和区间修改操作。 ## 原理 线段树的构建过程如下： 1. 将原数组划分为n个子区间， ......

定义 线段树分治是一种解决一类有插入、删除和整体查询操作的问题的方法。它是一种离线做法，通过在线段树上记录操作的时间区间来处理修改对询问的影响。每个操作被看作一个时间区间的修改，并在线段树上进行标记。然后通过深度优先搜索（DFS）依次执行这些操作，直到根节点来回答查询，并在离开时将其撤销。 题目 # ......

## 一.动态开点线段树 虽然思路简单，但对于一个习惯数组写法的人，这是一个比较难受的东西。 动态开点一般是用来解决空间上的问题的。 一般来说，普通的线段树是直接将一颗完整的线段建出来，但如碰到数据范围大或卡空间的时候，我们就只能在我们需要的时候再建，这个就叫做动态开点。（类似于 trie） ### ......

[也许更好的阅读体验](https://blog.csdn.net/Morning_Glory_JR/article/details/132194133?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22% ......

## 线段树补充 ### 线段树维护矩阵和 #### 矩阵快速幂 和普通快速幂同理 ```cpp int M; struct matrix { ll x[M+1][M+1]; matrix() { memset(x,0,sizeof(x)); } }; matrix multiply(matrix ......

## 基本思路 线段树合并其实就是简单的暴力合并就可以了。一般是运用于权值线段树。通常是在每个节点都需要要一颗线段树才能维护答案，且有多个节点时，会使用线段树合并。但每个节点所有的权值不能太多，如果都是比较满的二叉树的话，时间复杂度就会很高。 通常，加入值的数量跟节点数量在同一级别的话，时间复杂度是 ......

### 用途 李超线段树的用法非常固定，一般就是让你求对于给出的一些线段或直线中，对于某个x最大的y是那个。 通常可以用于斜率优化。 而其的时间复杂度是 $O(n\log n^2)$ ### 思路 注：下文默认是线段，因为直线也只用改一下就行了。 我们建立一颗线段树，每个节点保存在当前区间，当x=m ......

# Part 1：标记永久化 **一言以蔽之**：标记永久化就是不再下放标记，而是让标记永久地停留在线段树的节点上，统计答案时再考虑这些标记的影响 # Part 2：维护直线 我们以下面这道题为例子来进行讲解 ## [JSOI2008] Blue Mary开公司 （[题目传送门](https://w ......

# Part 1：知识点 - ### 前置知识：动态开点线段树 - 线段树合并是一个递归的过程。我们合并两棵线段树时，用两个指针 $p,q$ 从两个根节点出发，以递归的方式**同步遍历**两棵线段树。 1.若 $p,q$ 之一为空，则以非空的那个作为合并的节点 2.若 $p,q$ 均不为空，则递归合 ......

# 引入 ## 题目描述 给定$n$个数$a[1],a[2],a[3]...a[n]$,现在又下面两种操作： 1.询问区间$[x,y]$的和，并输出。 2.将下标为$x$的数增加$val$。 一共$x$此操作 $1\le n,m\le 100000$，保证在$int$范围内。 ### 方法一：暴力枚 ......

线段树 除了最后一层满二叉树，用堆（一维数组）来存树，一般来说，开4n的空间  #### build（int u, int l, int r） 将一段区间初始化为线段树 #### push up（） 由子节点更新父节 ......

### 题意： > 给定一个序列$a$，定义一次操作选择序列中一个元素$a[i]$， 使$a_i = \lfloor \frac{a_i}{2} \rfloor$，其中$a_i$为当前序列中的最大偶数，若没有则是最大奇数。 > > 有$q$组询问，每次给定$k, l, r$分别表示操作次数和操作区间 ......

### [题目传送门](https://www.luogu.com.cn/problem/P5524) ## solution 简单题。 我们正着做扫描线。 设 $t_i$ 表示位置 $i$ 最后一次进行二操作的时间，那么一操作就是交换 $t_x,t_y$ ，二操作就是区间复制。 对于三操作，开一个 ......

## 矩阵 我一向对矩阵是深恶痛绝的，难写是一点，更多是因为我总觉得发明矩阵的人觉得自己很酷。 （矩阵这玩意总是让我想不清楚本质 以至于我总想着以某些方法代替矩阵，以前喜欢用分治，那时认为矩阵的本质是分治，但是分治这玩意写出来奇丑无比，今天既然见到题解有类似的实现，便顺便梳理一下， 希望有更深的理解 ......

## [P3373 线段树模板 2](https://www.luogu.com.cn/problem/P3373) ![image-20230803010844370](https://zeoy-typora.oss-cn-hangzhou.aliyuncs.com/image-202308030 ......

## 线段树复健 OJ 上的题还没做完，下午再说（你 ### 概念 一种**二叉搜索树**，通过二叉树形结构储存数据，能够解决大部分与**区间操作**有关的问题，当然应用范围不止于区间操作。 原理是用二分（？）维护一定的区间。 ### 主体部分实现 #### 建树 考虑递归建树，一直二分直到只剩一个 ......

RT 感觉会模板就差不多了，可用作处理一些线段或直线的问题，转化过来的也可以。比如DP的斜率优化，直线的话只用一个log,线段要两个log。 [[HEOI2013] Segment](https://www.luogu.com.cn/problem/P4097 "[HEOI2013] Segment ......

> 「观前提醒」 > > 「文章仅供学习和参考，如有问题请在评论区提出」 [toc] ## 引入 **线段树（Segment Tree）**是算法竞赛中常用的用来维护区间信息的数据结构。 线段树可以在 $O(logN)$ 的时间复杂度内实现**单点修改、区间修改、区间查询**等操作。能够用来维护很多 ......