线段 区间

# $$\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 \ ......

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

因为以前搞的主席树基本都忘了，故写一篇帮助记忆。 前置芝士： [主席树](https://zhuanlan.zhihu.com/p/250565583) 我发现网上的大部分代码码风和我不同，我希望主席树的打法和线段树差不多，所以我找到了一个和线段树差不多的打法。 首先，主席树如果涉及到区间修改，会稍 ......

## 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$ 和 $ ......

原题：[洛谷P9533](https://www.luogu.com.cn/problem/P9533) ## 一道性质题 #### 不难发现，区间翻转操作是没有用的*（虽然比赛的时候想了好久www）* 首先，区间翻转要想对答案有贡献，一定是下边这种情况： **三个连续的区间：$A~|~B~|~C$ ......

import java.util.ArrayList; import java.util.TreeMap; import java.util.stream.IntStream; public class Main { public static void main(String[] args) { ......

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

给定长度为 $n$ 的字符串 $S$ 以及 $m$ 个区间 $[l_i, r_i]$，记 $T=S[l_1,r_1]+\cdots+S[l_m,r_m]$，其中 $S[x,y]$ 表示从第 $x$ 个字符到第 $y$ 个字符的子串。求如何重新排列 $S$ 中字符的顺序使得 $T$ 的字典序尽可能大。 ......

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

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

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

最近在思考半在线卷积的复杂度有没有可能进一步优化, 决定先理清类似的问题以寻求经验. ## 一区间合并 如果询问的时候不能进行半群运算, 显然我们需要在预处理阶段处理所有答案, 必须进行 $O(n^2)$ 次计算. ## 二区间合并 如果询问的时候可以进行一次半群运算, 则可以把序列每次在中点处折开 ......

就是个解方程。 #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个子区间， ......

## 1.定义与性质 区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。 令状态 $dp_{(i,j)}$ 表示将下标位置 $i$ 到 $j$ 的所有元素合并能获得的价值的最大值，那么 $dp_{(i,j)}=max\{dp ......

在网上胡乱找的一些关于并查集处理区间跳跃（也有叫区间覆盖/序列联通性，这类问题有没有什么统一叫法存疑？）的题目，或许能学习后成为一种套路 参考： [区间跳跃问题](https://www.cnblogs.com/TYH-TYH/p/10747781.html) ## [Knight Tourname ......

## [模板区间 dp](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P3146) - 一个长 $n(n \le 248)$ 的序列，选择数列中两个相邻且相等的元素，删去其中一个元素并使另一个元素的值 $+1$，求数次操作后数列中的最大值 - 将这看做 ......

# [1857E.Power of Points](https://codeforces.com/contest/1857/problem/E "Codeforces 1857E") ## Description: - $n$ 个数：$x_1,···,x_n$，从左向右扫，当 $s=x_i$ 时，可 ......

定义 线段树分治是一种解决一类有插入、删除和整体查询操作的问题的方法。它是一种离线做法，通过在线段树上记录操作的时间区间来处理修改对询问的影响。每个操作被看作一个时间区间的修改，并在线段树上进行标记。然后通过深度优先搜索（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 ......

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。 示例 1： 输入：intervals = [[1,3],[2,6],[8,10] ......

Smiling & Weeping 你站在桥上看风景， 看风景的人在楼上看你。 明月装饰了你的窗子， 你装饰了别人的梦。 题目： 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 题目链接： ......