线段树1 - 洛谷保存站

# 基础
树状数组的原理是二进制，而线段树的原理是分治。并且都是现存区间答案，再合并进行分析。

树状数组能完成的，线段树都能完成；线段树能完成的，树状数组不一定能完成。

线段树因为需要传参，所以需要带一个大常数。

普通线段树可以解决的事有：

1. 区间和
2. 区间 $\gcd$
3. 区间最值
4. 区间异或和
## 单点修改+区间查询
这是很基础的线段树，步骤是：

1. 建树
2. 单点修改
3. 区间查询

**重点**

$\{k , l , r\}$ 表示的是线段树的节点信息，一般通过重新递归，然后 $sum_k=sum_{sonl} + sum_{sonr}$。

单点查询时，截止条件是 `i == j`，记得只要修改了就要 `push_up`。

区间查询时，如果区间在范围内，即 `if(L <= l && r <= R)`，则结果需要加上。

关于线段树，建树时复杂度是 $O(4n)$，单点查询时复杂度是 $O(\lg n)$，区间查询时复杂度是 $O(\lg n)$。

注意要开四倍空间。
## 区间修改+区间查询
区间修改的话，就需要用到懒标记。

因为查询是需要时间，可以边查询，边修改。查询到对应的点，那么将标记发给儿子节点。

**注意**

使用标记时，懒标记更新，答案也要更新。

在修改和查询子树时，如果可以，必须下发。

# 例题
现在来看代码实现吧！
## [U438237 ١١(❛ᴗ❛)【树状数组+线段树】-模板（单点修改+区间查询）](https://www.luogu.com.cn/problem/U438237)
简单的单点修改+区间查询模版。

线段树上面点的编号本人喜欢用层序遍历的顺序，则算左右儿子的函数用宏定义来求。
```cpp
#define lson(x) (x << 1) 
#define rson(x) ((x << 1) | 1) 
```
在算左右儿子的贡献时，为了简化代码，我用了一个函数。
```cpp
void push_up(int k)
{
	sum[k] = sum[lson(k)] + sum[rson(k)] ;
}
```
建树部分，很像二分，分成左右两段，当左右端点都指着一个点，那么算答案。
```cpp
if(l == r)
{
  sum[k] = a[l] ; // 线段树端点的编号是k
  return ;
}
```
记得调用函数 `push_up`。建树总体代码如下。
```cpp
void build(int k , int l , int r)
{
	if(l == r)
	{
		sum[k] = a[l] ;
		return ;
	}
	int mid = l + r >> 1 ;
	build(lson(k) , l , mid) ;
	build(rson(k) , mid + 1 , r) ;
	push_up(k) ;
}
```
修改部分，和建树差不多，只是遍历左右两边有条件了。
```cpp
void update(int v , int x , int k , int l , int r)
{
	if(l == r)
	{
		sum[k] += x ; // 修改
		return ;
	}
	int mid = l + r >> 1 ;
	if(v <= mid) // 在左边
	{
		update(v , x , lson(k) , l , mid) ;
	}
	if(v > mid) // 在右边
	{
		update(v , x , rson(k) , mid + 1 , r) ;
	}
	push_up(k) ; 
}
```
在查询时，因为是区间查询，所以遍历条件和结束条件都不一样，直接看代码。
```cpp
int ans(int L , int R , int k , int l , int r)
{
	if(L <= l && r <= R)
	{
		return sum[k] ;
	}
	int res = 0 ;
	int mid = l + r >> 1 ;
	if(L <= mid)
	{
		res += ans(L , R , lson(k) , l , mid) ;
	}
	if(R > mid)
	{
		res += ans(L , R , rson(k) , mid + 1 , r) ;
	}
	return res ;
}
```
那么，本体代码就出来了。
```cpp
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
#define debug(...){\
	cout<<"debug in function "<<__FUNCTION__<<",line "<<__LINE__<<"\n";\
	string s=#__VA_ARGS__,s2="";\
	vector<string>v;\
	for(auto i:s){\
		if(i==','){\
			v.push_back(s2);\
			s2="";\
		}else{\
			s2+=i;\
		}\
	}\
	v.push_back(s2);\
	vector<int>v2={__VA_ARGS__};\
	for(int i=0;i<v.size()-1;i++){\
		cout<<v[i]<<"="<<v2[i]<<"\n";\
	}\
	cout<<v[v.size()-1]<<"="<<v2[v2.size()-1]<<"\n\n";\
}
using namespace std ;
const int kMaxN = 1e6 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int n , q ;
int a[kMaxN] , sum[kMaxN << 2] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
inline int read()
{
    int x = 0 , f = 1 ;
    char ch = getchar() ;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1 ;
        ch = getchar() ;
    }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0' , ch = getchar() ;
    return x * f ;
}
void write(int x)
{
    if(x < 0) putchar('-') , x = -x ;
    if(x > 9) write(x / 10) ;
    putchar(x % 10 + '0') ;
}
#define lson(x) (x << 1) 
#define rson(x) ((x << 1) | 1) 
void push_up(int k)
{
	sum[k] = sum[lson(k)] + sum[rson(k)] ;
}
void build(int k , int l , int r)
{
	if(l == r)
	{
		sum[k] = a[l] ;
		return ;
	}
	int mid = l + r >> 1 ;
	build(lson(k) , l , mid) ;
	build(rson(k) , mid + 1 , r) ;
	push_up(k) ;
}
void update(int v , int x , int k , int l , int r)
{
	if(l == r)
	{
		sum[k] += x ;
		return ;
	}
	int mid = l + r >> 1 ;
	if(v <= mid)
	{
		update(v , x , lson(k) , l , mid) ;
	}
	if(v > mid)
	{
		update(v , x , rson(k) , mid + 1 , r) ;
	}
	push_up(k) ;
}
int ans(int L , int R , int k , int l , int r)
{
	if(L <= l && r <= R)
	{
		return sum[k] ;
	}
	int res = 0 ;
	int mid = l + r >> 1 ;
	if(L <= mid)
	{
		res += ans(L , R , lson(k) , l , mid) ;
	}
	if(R > mid)
	{
		res += ans(L , R , rson(k) , mid + 1 , r) ;
	}
	return res ;
}
void Read()
{
	cin >> n >> q ;
}
void work()
{
  Read() ;
	for( int i = 1 ; i <= n ; i++ )
	{
		cin >> a[i] ;
	}
	build(1 , 1 , n) ;
	while(q--)
	{
		int op ;
		cin >> op ;
		if(op == 1)
		{
			int x , y ;
			cin >> x >> y ;
			update(x , y , 1 , 1 , n) ;
		}
		else
		{
			int l , r ;
			cin >> l >> r ;
			cout << ans(l , r , 1 , 1 , n) << "\n" ;
		}
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}
```
## [P4392 [BalticOI 2007] Sound 静音问题](https://www.luogu.com.cn/problem/P4392)
题面比较抽象，直接看输出格式。

这道题就是求区间最大值和最小值。

维护**两颗**线段树，把算贡献和查询时算答案时，分别改成取最大值和最小值即可。

```cpp
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
#define debug(...){\
	cout<<"debug in function "<<__FUNCTION__<<",line "<<__LINE__<<"\n";\
	string s=#__VA_ARGS__,s2="";\
	vector<string>v;\
	for(auto i:s){\
		if(i==','){\
			v.push_back(s2);\
			s2="";\
		}else{\
			s2+=i;\
		}\
	}\
	v.push_back(s2);\
	vector<int>v2={__VA_ARGS__};\
	for(int i=0;i<v.size()-1;i++){\
		cout<<v[i]<<"="<<v2[i]<<"\n";\
	}\
	cout<<v[v.size()-1]<<"="<<v2[v2.size()-1]<<"\n\n";\
}
using namespace std ;
const int kMaxN = 1e6 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int n , m , c ;
int a[kMaxN] , sum_max[kMaxN << 2] , sum_min[kMaxN << 2] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
inline int read()
{
    int x = 0 , f = 1 ;
    char ch = getchar() ;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1 ;
        ch = getchar() ;
    }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0' , ch = getchar() ;
    return x * f ;
}
void write(int x)
{
    if(x < 0) putchar('-') , x = -x ;
    if(x > 9) write(x / 10) ;
    putchar(x % 10 + '0') ;
}
#define lson(x) (x << 1) 
#define rson(x) ((x << 1) | 1) 
void push_up_max(int k)
{
	sum_max[k] = max(sum_max[lson(k)] , sum_max[rson(k)]) ;
}
void push_up_min(int k)
{
	sum_min[k] = min(sum_min[lson(k)] , sum_min[rson(k)]) ;
}
void build_max(int k , int l , int r)
{
	if(l == r)
	{
		sum_max[k] = a[l] ;
		return ;
	}
	int mid = l + r >> 1 ;
	build_max(lson(k) , l , mid) ;
	build_max(rson(k) , mid + 1 , r) ;
	push_up_max(k) ;
}
void build_min(int k , int l , int r)
{
	if(l == r)
	{
		sum_min[k] = a[l] ;
		return ;
	}
	int mid = l + r >> 1 ;
	build_min(lson(k) , l , mid) ;
	build_min(rson(k) , mid + 1 , r) ;
	push_up_min(k) ;
}
int ans_max(int L , int R , int k , int l , int r)
{
	if(L <= l && r <= R)
	{
		return sum_max[k] ;
	}
	int maxn = 0 ;
	int mid = l + r >> 1 ;
	if(L <= mid)
	{
		maxn = max(maxn , ans_max(L , R , lson(k) , l , mid)) ;
	}
	if(R > mid)
	{
		maxn = max(maxn , ans_max(L , R , rson(k) , mid + 1 , r)) ;
	}
	return maxn ;
}
int ans_min(int L , int R , int k , int l , int r)
{
	if(L <= l && r <= R)
	{
		return sum_min[k] ;
	}
	int minn = INF ;
	int mid = l + r >> 1 ;
	if(L <= mid)
	{
		minn = min(minn , ans_min(L , R , lson(k) , l , mid)) ;
	}
	if(R > mid)
	{
		minn = min(minn , ans_min(L , R , rson(k) , mid + 1 , r)) ;
	}
	return minn ;
}
void Read()
{
	cin >> n >> m >> c ;
}
void work()
{
  Read() ;
	for( int i = 1 ; i <= n ; i++ )
	{
		cin >> a[i] ;
	}
	build_max(1 , 1 , n) ;
	build_min(1 , 1 , n) ;
	bool flag = 0 ;
	F(i , 1 , n , 1)
	{
		if(i + m - 1 > n) break ;
		if(ans_max(i , i + m - 1 , 1 , 1 , n) - ans_min(i , i + m - 1 , 1 , 1 , n) <= c)
		{
			cout << i << "\n" ;
			flag = 1 ;
		}
	} 
	if(!flag) cout << "NONE" ;
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}
```
## [P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372)
懒标记的原理上文已经说过了，那么看代码中的改动部分。

新加入专门计算懒标记和答案的函数。
```cpp
void update_son(int k , int l , int r , ll v)
{
	lazy[k] += v ;
	t[k] += (r - l + 1) * v ;
}
```
新加入把懒标记下发的函数。
```cpp
void push_down(int k , int l , int r)
{
	if(!lazy[k]) return ;
	int mid = l + r >> 1 ;
	update_son(lson(k) , l , mid , lazy[k]) ;
	update_son(rson(k) , mid + 1 , r , lazy[k]) ;
	lazy[k] = 0 ;
}
```
建树是没有改动的。

修改的最终结束条件改变，遍历前，要分发懒标记。
```cpp
void update(int L , int R , ll x , int k , int l , int r)
{
	if(L <= l && r <= R)
	{
    update_son(k , l , r , x) ;
		return ;
	}
	int mid = l + r >> 1 ;
	push_down(k , l , r) ;
	if(L <= mid)
	{
		update(L , R , x , lson(k) , l , mid) ;
	}
	if(R > mid)
	{
		update(L , R , x , rson(k) , mid + 1 , r) ;
	}
	push_up(k) ;
}
```
算答案时，遍历前要分发懒标记。
```cpp
ll ans(int L , int R , int k , int l , int r)
{
	if(L <= l && r <= R)
	{
		return t[k] ;
	}
	ll res = 0 ;
	int mid = l + r >> 1 ;
	push_down(k , l , r) ;
	if(L <= mid)
	{
		res += ans(L , R , lson(k) , l , mid) ;
	}
	if(R > mid)
	{
		res += ans(L , R , rson(k) , mid + 1 , r) ;
	}
	return res ;
}
```
则这题的代码如下。
```cpp
//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
#define debug(...){\
	cout<<"debug in function "<<__FUNCTION__<<",line "<<__LINE__<<"\n";\
	string s=#__VA_ARGS__,s2="";\
	vector<string>v;\
	for(auto i:s){\
		if(i==','){\
			v.push_back(s2);\
			s2="";\
		}else{\
			s2+=i;\
		}\
	}\
	v.push_back(s2);\
	vector<int>v2={__VA_ARGS__};\
	for(int i=0;i<v.size()-1;i++){\
		cout<<v[i]<<"="<<v2[i]<<"\n";\
	}\
	cout<<v[v.size()-1]<<"="<<v2[v2.size()-1]<<"\n\n";\
}
using namespace std ;
const int kMaxN = 1e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int n , q ;
ll t[kMaxN << 2] , a[kMaxN] , lazy[kMaxN << 2] ;
inline ll ksm(ll a , ll b)
{
	ll mul = 1 ;
	while(b)
	{
		if(b & 1) mul *= a , mul %= MOD ;
		a *= a ;
		a %= MOD ;
		b >>= 1 ;
	}
	return mul ;
}
inline int read()
{
    int x = 0 , f = 1 ;
    char ch = getchar() ;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1 ;
        ch = getchar() ;
    }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0' , ch = getchar() ;
    return x * f ;
}
void write(int x)
{
    if(x < 0) putchar('-') , x = -x ;
    if(x > 9) write(x / 10) ;
    putchar(x % 10 + '0') ;
}
#define lson(x) (x << 1) 
#define rson(x) ((x << 1) | 1) 
void push_up(int k)
{
	t[k] = t[lson(k)] + t[rson(k)] ;
}
void update_son(int k , int l , int r , ll v)
{
	lazy[k] += v ;
	t[k] += (r - l + 1) * v ;
}
void push_down(int k , int l , int r)
{
	if(!lazy[k]) return ;
	int mid = l + r >> 1 ;
	update_son(lson(k) , l , mid , lazy[k]) ;
	update_son(rson(k) , mid + 1 , r , lazy[k]) ;
	lazy[k] = 0 ;
}
void build(int k , int l , int r)
{
	lazy[k] = 0 ;
	if(l == r)
	{
		t[k] = a[l] ;
		return ;
	}
	int mid = l + r >> 1 ;
	build(lson(k) , l , mid) ;
	build(rson(k) , mid + 1 , r) ;
	push_up(k) ;
}
void update(int L , int R , ll x , int k , int l , int r)
{
	if(L <= l && r <= R)
	{
    update_son(k , l , r , x) ;
		return ;
	}
	int mid = l + r >> 1 ;
	push_down(k , l , r) ;
	if(L <= mid)
	{
		update(L , R , x , lson(k) , l , mid) ;
	}
	if(R > mid)
	{
		update(L , R , x , rson(k) , mid + 1 , r) ;
	}
	push_up(k) ;
}
ll ans(int L , int R , int k , int l , int r)
{
	if(L <= l && r <= R)
	{
		return t[k] ;
	}
	ll res = 0 ;
	int mid = l + r >> 1 ;
	push_down(k , l , r) ;
	if(L <= mid)
	{
		res += ans(L , R , lson(k) , l , mid) ;
	}
	if(R > mid)
	{
		res += ans(L , R , rson(k) , mid + 1 , r) ;
	}
	return res ;
}
void Read()
{
	cin >> n >> q ;
}
void work()
{
  Read() ;
	for( int i = 1 ; i <= n ; i++ )
	{
		cin >> a[i] ;
	}
	build(1 , 1 , n) ;
	while(q--)
	{
		int op ;
		cin >> op ;
		if(op == 1)
		{
			int l , r ;
			ll y ;
			cin >> l >> r >> y ;
			update(l , r , y , 1 , 1 , n) ;
		}
		else
		{
			int l , r ;
			cin >> l >> r ;
			cout << ans(l , r , 1 , 1 , n) << "\n" ;
		}
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

```

正在渲染内容...