首页 > 其他分享 >2022.12.20 线段树复习笔记（未完待续）

2022.12.20 线段树复习笔记（未完待续）

时间：2022-12-20 14:13:49浏览次数：63  
标签：线段 20 int sum tr 节点 未完待续 ll 2022.12

线段树原理及存储：

image
如图，1即为根节点，存储着[1,5]的整个区间和，‘1’为左边界，‘5’为右边界，所以此节点表示的是[1,5]这个区间。
线段树的每个节点向下二分，左儿子的编号为此节点 \(× 2\)，右儿子的编号为此节点 \(× 2 + 1\)，也就是数组存完全二叉树的做法。
所以，线段树可以直接用一个结构体来存：

struct Node{
	int l, r;
	ll sum; //和最好用long long来存，因为一般会爆int
}tr[4 * N]; //线段树节点个数最多为4倍n

线段树的单点修改，区间查询

线段树的建立

从根节点开始建树，更新当前节点左右边界信息后递归建立左右儿子。
如果当前节点为叶节点，即l == r时，那么它所代表的这个区间就只有一个值，就将此节点的sum更新为这一个值（即下面的a[l]）。
每层递归的最后，再把当前节点的sum更新为左儿子的sum加上右儿子的sum。
因此，我们一般会写一个pushdown函数，用来往上更新。

void pushup(int u){
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

这样，在build函数的最后，我们就可以直接用一个pushup函数来更新当前节点的sum了。

void build(int u, int l, int r){
	tr[u]={l, r};
	if(l == r){
		tr[u].sum = a[l];
		return;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

线段树的单点修改（很少用）

单点修改很简单，从根节点往下二分，逐步锁定要修改的节点，如果为叶节点，就直接修改即可。
然后最后还要用子节点的信息更新自己，保证值正确。
具体代码如下：

void update(int u, int x, int k){	//节点编号为u，要将第x个节点加上k
	if(tr[u].l == tr[u].r){		//如果是叶节点，说明这就是要找的，直接加上就可以了
		tr[u].sum += k;
		return;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;//还没找到就向下二分，找出mid
	if(x <= mid) update(u << 1, x, k);//如果x在左半边，就向左半边递归
	else update(u << 1 | 1, x, k);	//否则向右递归
	pushup(u);			//更新当前节点信息
}

线段树一般不会这么用，因为如果只是单点修改，区间查询的话肯定就用树状数组，无论是在代码长度，编码和调试难度，乃至时间，空间上都是树状数组更优。
这里只是简单做一个讲解，方便理解后面的区间修改。

线段树的区间查询

查询时类似，也是从根节点开始递归。
但是这次要应对的是一个区间，所以略有不同。
具体代码如下：

ll query(int u, int l, int r){		//节点编号为u，要查询[l, r]这个区间
	if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
	//如果当前区间已经全部被包含在要查询的区间中，就直接返回sum即可
	
	ll sum = 0;	//记录和
	int mid = tr[u].l + tr[u].r >> 1;	//同理二分
	if(l <= mid) sum += query(u << 1, l, r);
	//如果要查询的区间与左半部分有交集，就要加上左半部分的和，继续递归左边
	if(r > mid) sum += query(u << 1 | 1, l, r);
	//如果与右边有交集就同理加上右边并递归。
	//这里注意两个if一定要分开写，不能直接else，因为有可能要查找的区间卡在中间，左右两边都要加一遍
	return sum;	//最后一定要记得返回sum的值
}

最后的整合代码（可AC洛谷 P3374 【模板】树状数组 1）

线段树一般不会拿来单点修改，这里只是从简单说起，后面的区间修改要涉及到 \(\texttt{lazy_tag}\)(懒标记) 才是重点。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 500010;

int n, m;
int a[N];

struct Node{
	int l, r;
	ll sum;
}tr[4 * N]; 

void pushup(int u){
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r){
	tr[u]={l, r};
	if(l == r){
		tr[u].sum = a[l];
		return;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void update(int u, int x, int k){
	if(tr[u].l == tr[u].r){
		tr[u].sum += k;
		return;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid) update(u << 1, x, k);
	else update(u << 1 | 1, x, k);
	pushup(u);
}

ll query(int u, int l, int r){
	if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
	
	ll sum = 0;
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) sum += query(u << 1, l, r);
	if(r > mid) sum += query(u << 1 | 1, l, r);
	return sum;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	
	build(1, 1, n);
	
	int op, x, y;
	for(int i = 1; i <= m; ++i){
		scanf("%d%d%d", &op, &x, &y);
		if(op == 1) update(1, x, y);
		else printf("%lld\n", query(1, x, y));
	}
	return 0;
}

线段树的区间修改，区间查询

区间修改相对于单点修改，就要复杂一些了。
我们首先考虑如果向单点修改那样，对区间中的每个元素注意修改，那就要修改 \(n\) 次，每次修改复杂度为 \(\mathcal{O}(\log n)\) ，那总复杂度就到了 \(\mathcal{O}(n\log n)\) ，比暴力还差，那还玩啥啊？
于是，这种情况下，\(\texttt{lazy_tag}\) 它就应运而生了。

\(\texttt{lazy_tag}\) 的具体原理

\(\texttt{lazy_tag}\) 其实就是在每次修改到一个完全被包含的节点的时候，就直接更改这个节点上的区间和sum，然后再这个节点上打一个标记（懒标记，即 \(\texttt{lazy_tag}\) ）。在之后再查询到这个节点，而且需要继续往下分的时候，再把它的懒标记往下传递到它的左右两个子节点中，这样就避免了大量不必要的操作，大大降低了时间复杂度。

区间修改，区间查询的代码

首先，在线段树的每个节点中多存一个add，表示当前的 \(\texttt{lazy_tag}\) ，即这个节点的每个子节点的区间中的每个元素还要加上add。
然后，我们还要专门写一个pushdown函数，来把懒标记下传。

void pushdown(int u){
	Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
	//为了方便，先定义一下根节点，左、右子节点
	if(root.add){	//有标记才下传
		left.sum += (left.r - left.l + 1) * root.add;
		right.sum += (right.r - right.l + 1) * root.add;
		//左右节点的sum和加上它们的区间长度乘上根节点的add
		left.add += root.add;
		right.add += root.add;
		//左右节点的add也要加上根节点的add
		root.add = 0;
		//根节点的add记得清零
	}
}

然后就是区间修改的函数

void update(int u, int l, int r, int k){
	if(l <= tr[u].l && tr[u].r <= r){
		tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
		tr[u].add += k;
		//如果当前节点已被所求区间全部包含，直接把此节点的sum更新，并把add加上k，然后直接返回
		return;
	}
	
	pushdown(u);	//在二分之前先看看是否需要下传标记
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) update(u << 1, l, r, k);
	if(r > mid) update(u << 1 | 1, l, r, k);
	//后面和之前的单点修改同理，只是注意这里的l, r, k都是直接传下去的，因为后面的修改也是看整个所求区间
	pushup(u);	//最后记得要pushup一下
}

还有区间查询的函数，有一些改动

ll query(int u, int l, int r){
	if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
	
	pushdown(u);	//其实就只是在需要分开算的时候pushdown一下就可以了(*^v^*)
	ll sum = 0;
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) sum += query(u << 1, l, r);
	if(r > mid) sum += query(u << 1 | 1, l, r);
	return sum;
}

整合代码（可AC洛谷 P3372 【模板】线段树 1）

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 100010;

int n, m;
int a[N];

struct Node{
    int l, r;
    ll add;	//add最好也用long long
    ll sum;
}tr[4 * N];

void pushup(int u){
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r){
	tr[u]={l, r, 0};	//记得把add初始化为0
	if(l == r){
		tr[u].sum = a[l];
		return;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void pushdown(int u){
	Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
	if(root.add){
		left.sum += (left.r - left.l + 1) * root.add;
		right.sum += (right.r - right.l + 1) * root.add;
		left.add += root.add;
		right.add += root.add;
		root.add = 0;
	}
}

void update(int u, int l, int r, int k){
	if(l <= tr[u].l && tr[u].r <= r){
		tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
		tr[u].add += k;
		return;
	}
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) update(u << 1, l, r, k);
	if(r > mid) update(u << 1 | 1, l, r, k);
	pushup(u);
}

ll query(int u, int l, int r){
	if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
	
	pushdown(u);
	ll sum = 0;
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) sum += query(u << 1, l, r);
	if(r > mid) sum += query(u << 1 | 1, l, r);
	return sum;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    build(1, 1, n);

    int op, x, y, k;
    while(m--){
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1){
            scanf("%d", &k);
            update(1, x, y, k);
        }
        else{
            printf("%lld\n", query(1, x, y));
        }
    }
    
    return 0;
}

线段树的综合应用

接下来，以洛谷P6242 【模板】线段树 3（超级毒瘤）为例，来看一下线段树的综合应用。

先来看一下此题题意，很熟悉的题面：

题目描述

给出一个长度为 \(n\) 的数列 \(A\)，同时定义一个辅助数组 \(B\)，\(B\) 开始与 \(A\) 完全相同。接下来进行了 \(m\) 次操作，操作有五种类型，按以下格式给出：

  • 1 l r k：对于所有的 \(i\in[l,r]\)，将 \(A_i\) 加上 \(k\)（\(k\) 可以为负数）。
  • 2 l r v：对于所有的 \(i\in[l,r]\)，将 \(A_i\) 变成 \(\min(A_i,v)\)。
  • 3 l r：求 \(\sum\limits_{i=l}^{r}A_i\)。
  • 4 l r：对于所有的 \(i\in[l,r]\)，求 \(A_i\) 的最大值。
  • 5 l r：对于所有的 \(i\in[l,r]\)，求 \(B_i\) 的最大值。

在每一次操作后，我们都进行一次更新，让 \(B_i\gets\max(B_i,A_i)\)。

数据规模与约定

  • 对于全部测试数据，保证 \(1\leq n,m\leq 5\times 10^5\)，\(-5\times10^8\leq A_i\leq 5\times10^8\)，\(op\in[1,5]\)，\(1 \leq l\leq r \leq n\)，\(-2000\leq k\leq 2000\)，\(-5\times10^8\leq v\leq 5\times10^8\)。

初看此题，挺简单啊，就是操作有点多（竟然还是紫题）。

但是你细看这个操作，2 l r v：对于所有的 \(i\in[l,r]\)，将 \(A_i\) 变成 \(\min(A_i,v)\)。

怎么修改？

这也没法 \(\texttt{lazy_tag}\) 大法呀。

要是硬修改，那么恭喜你写出了一个区间修改复杂度为 \(\mathcal{O}(n\log n)\) 的优秀线段树。

这跟没加 \(\texttt{lazy_tag}\) 的区间加不一样了吗...

那怎么办？

就要用到大名鼎鼎的 吉司机线段树 了！

其实也跟普通线段树没什么区别。

只是在线段树中多维护两个值：

次大值 和 最大值的个数。

下面分别用 \(sem\) 和 \(cnt\) 表示（最大值为 \(maxa\)）。

这有什么用呢？

在进行修改操作时，遇到某一个节点（代表了一个区间），要对于所有的 \(i\in[l,r]\)，将 \(A_i\) 变成 \(\min(A_i,v)\)：

  • 当此区间的 \(maxa \leqslant v\) 时，此区间肯定不用修改，直接 return;
  • 当此区间满足 \(sem \leqslant v < maxa\) 时，就只用将所有最大值改为 \(cnt\) ，将 \(sum\) 减去 \(cnt \times (maxa - v)\) ，再打上标记即可。
  • 否则无法修改，继续向左右子节点递归。

那么，这样我们一次操作的复杂度就是 \(\mathcal{O}(\log^2 n)\) （这是结论，具体证明就不说了）

接下来，我们就来看一下具体的实现。

结点维护的信息

因为这题实属毒瘤，所以我们需要维护 \(\rm{4}\) 个 \(\texttt{lazy_tag}\) :

  • \(\rm{add1}\) : \(A\) 数组中最大值要加的
  • \(\rm{add2}\) : \(A\) 数组中非最大值要加的
  • \(\rm{add3}\) : \(B\) 数组中最大值要加的（其实是 \(A\) 历史中最大值加的最多的一次）
  • \(\rm{add4}\) : \(B\) 数组中非最大值要加的（其实是 \(A\) 历史中非最大值加的最多的一次）

\(\text{Q} :\) 为什么要用 \(\rm{4}\) 个 \(\texttt{lazy_tag}\) 呢？

\(\text{A} :\) 因为当进行取 \(\min\) 操作时，节点只会更改最大值，这样最大值要加的和非最大值要加的就不一样了，所以需要分最大值和非最大值，于是就被迫使用 \(\rm{4}\) 个 \(\texttt{lazy_tag}\) 。

\(\text{Code}\)

struct Node{
	int l, r;
	ll sum, add1, add2, add3, add4;
	ll maxa, maxb, sem;
    //不开 long long 见祖宗
	int cnt;
}tr[4 * N];

而真正折磨人的，在后面。

修改操作实现

这里一定要仔细理解，有很多分类讨论，也容易被误导。

  • \(\rm{pushup}\)

inline void pushup(int u){
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
	tr[u].maxa = Max(tr[u << 1].maxa, tr[u << 1 | 1].maxa);
	tr[u].maxb = Max(tr[u << 1].maxb, tr[u << 1 | 1].maxb);
    
	if(tr[u << 1].maxa > tr[u << 1 | 1].maxa){
        // 最大值在左边
		tr[u].sem = Max(tr[u << 1].sem, tr[u << 1 | 1].maxa);
        // 那么次大值就是左次大值和右最大值中大的一个
		tr[u].cnt = tr[u << 1].cnt;
        // 同时最大值的个数就是左子节点中最大值的个数
	}
	else if(tr[u << 1].maxa == tr[u << 1 | 1].maxa){
        // 左右两边最大值相同的这种情况需要特判一下
		tr[u].sem = Max(tr[u << 1].sem, tr[u << 1 | 1].sem);
		tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
        // 这里最大值的个数就是两边的 cnt 加起来了
	}
	else{
        // 同上，就是最大值在右边的情况
		tr[u].sem = Max(tr[u << 1].maxa, tr[u << 1 | 1].sem);
		tr[u].cnt = tr[u << 1 | 1].cnt;
	}
}

  • \(\rm{pushdown}\)

inline void pushdown(int u){
	ll maxn = Max(tr[u << 1].maxa, tr[u << 1 | 1].maxa);
	if(tr[u << 1].maxa == maxn) change(u << 1, tr[u].add1, tr[u].add2, tr[u].add3, tr[u].add4);
    // 当最大值在左边时，4 个 lazy_tag 可直接传入 change (change的定义见下)
	else change(u << 1, tr[u].add2, tr[u].add2, tr[u].add4, tr[u].add4);
    // 当最大值不在左边时，就全都是非最大值，传入两个非最大值的 lazy_tag
	if(tr[u << 1 | 1].maxa == maxn) change(u << 1 | 1, tr[u].add1, tr[u].add2, tr[u].add3, tr[u].add4);
	else change(u << 1 | 1, tr[u].add2, tr[u].add2, tr[u].add4, tr[u].add4);
    // 此处同理
    
	tr[u].add1 = tr[u].add2 = tr[u].add3 = tr[u].add4 = 0;
    // 记得清空
}

  • \(\rm{change}\)

为了方便，定义一个 \(\rm{change}\) 函数：

inline void change(int u, ll a1, ll a2, ll a3, ll a4){
    /*
    a1：A 数组中最大值要加的
    a2：A 数组中非最大值要加的
    a3：B 数组中最大值要加的
    a4：B 数组中非最大值要加的
    */
	tr[u].sum += a2 * (tr[u].r - tr[u].l + 1 - tr[u].cnt) + a1 * tr[u].cnt;
	tr[u].maxb = Max(tr[u].maxb, tr[u].maxa + a3);
    // 因为 a3 实质上是 A 历史中最大值加的最多的一次，所以此处应与 tr[u].maxa + a3 比较取 max
	tr[u].add3 = Max(tr[u].add3, tr[u].add1 + a3);
	tr[u].add4 = Max(tr[u].add4, tr[u].add2 + a4);
    // 此处同理
	tr[u].maxa += a1;
	if(tr[u].sem != -1e16) tr[u].sem += a2;
    // 只有当此节点存在次大值时更新
	tr[u].add1 += a1;
	tr[u].add2 += a2;
    // 这两处更新一定要放在最后，因为前面的更新要用到这两个变量
}

  • $ A_i\gets\min(A_i,v)$

void update_min(int u, int l, int r, int k){
	if(tr[u].maxa <= k) return;
    // 此时修改肯定不会影响到此节点，直接不管 (返回)
	if(l <= tr[u].l && tr[u].r <= r && tr[u].sem <= k){
        // 注意添加一个直接修改的条件：tr[u].sem <= k
		ll t = tr[u].maxa - k;
        // 最好先记录减小值
		tr[u].maxa = k;
		tr[u].sum -= tr[u].cnt * t;
		tr[u].add1 -= t;
       	// 这应该没什么好说的了...(-_-')
		return;
	}
	
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(l <= mid) update_min(u << 1, l, r, k);
	if(r > mid) update_min(u << 1 | 1, l, r, k);
	pushup(u);
}

总结

其他就没什么难的了，查询之类都很容易。

\(\text{完整 Code}\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 500010;

int n, m;
int a[N];

struct Node{
	int l, r;
	ll sum, add1, add2, add3, add4;
	ll maxa, maxb, sem;
	int cnt;
}tr[4 * N];

// 个人习惯，手写 Min, Max 函数
inline ll Max(ll a, ll b){return a > b ? a : b;}
inline ll Min(ll a, ll b){return a < b ? a : b;}

inline void pushup(int u){
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
	tr[u].maxa = Max(tr[u << 1].maxa, tr[u << 1 | 1].maxa);
	tr[u].maxb = Max(tr[u << 1].maxb, tr[u << 1 | 1].maxb);
	if(tr[u << 1].maxa > tr[u << 1 | 1].maxa){
		tr[u].sem = Max(tr[u << 1].sem, tr[u << 1 | 1].maxa);
		tr[u].cnt = tr[u << 1].cnt;
	}
	else if(tr[u << 1].maxa == tr[u << 1 | 1].maxa){
		tr[u].sem = Max(tr[u << 1].sem, tr[u << 1 | 1].sem);
		tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
	}
	else{
		tr[u].sem = Max(tr[u << 1].maxa, tr[u << 1 | 1].sem);
		tr[u].cnt = tr[u << 1 | 1].cnt;
	}
}

inline void change(int u, ll a1, ll a2, ll a3, ll a4){
	tr[u].sum += a2 * (tr[u].r - tr[u].l + 1 - tr[u].cnt) + a1 * tr[u].cnt;
	tr[u].maxb = Max(tr[u].maxb, tr[u].maxa + a3);
	tr[u].add3 = Max(tr[u].add3, tr[u].add1 + a3);
	tr[u].add4 = Max(tr[u].add4, tr[u].add2 + a4);
	tr[u].maxa += a1;
	if(tr[u].sem != -1e16) tr[u].sem += a2;
	tr[u].add1 += a1;
	tr[u].add2 += a2;
}

inline void pushdown(int u){
	ll maxn = Max(tr[u << 1].maxa, tr[u << 1 | 1].maxa);
	if(tr[u << 1].maxa == maxn) change(u << 1, tr[u].add1, tr[u].add2, tr[u].add3, tr[u].add4);
	else change(u << 1, tr[u].add2, tr[u].add2, tr[u].add4, tr[u].add4);
	if(tr[u << 1 | 1].maxa == maxn) change(u << 1 | 1, tr[u].add1, tr[u].add2, tr[u].add3, tr[u].add4);
	else change(u << 1 | 1, tr[u].add2, tr[u].add2, tr[u].add4, tr[u].add4);
	tr[u].add1 = tr[u].add2 = tr[u].add3 = tr[u].add4 = 0;
}

void build(int u, int l, int r){
    // 后面这几个处初值要注意 (栽跟头 * n)
	tr[u].l = l, tr[u].r = r;
	tr[u].add1 = tr[u].add2 = tr[u].add3 = tr[u].add4 = 0;
	if(l == r){
		tr[u].sum = tr[u].maxa = tr[u].maxb = a[l];
		tr[u].cnt = 1;
		tr[u].sem = -1e16;
		return;
	}
	
	int mid = (l + r) >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void update_add(int u, int l, int r, int k){
	if(l <= tr[u].l && tr[u].r <= r){
        // 此处可以直接调用 change 偷懒
		change(u, k, k, k, k);
		return;
	}
	
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(l <= mid) update_add(u << 1, l, r, k);
	if(r > mid) update_add(u << 1 | 1, l, r, k);
	pushup(u);
}

void update_min(int u, int l, int r, int k){
	if(tr[u].maxa <= k) return;
	if(l <= tr[u].l && tr[u].r <= r && tr[u].sem <= k){
		ll t = tr[u].maxa - k;
		tr[u].maxa = k;
		tr[u].sum -= tr[u].cnt * t;
		tr[u].add1 -= t;
		return;
	}
	
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(l <= mid) update_min(u << 1, l, r, k);
	if(r > mid) update_min(u << 1 | 1, l, r, k);
	pushup(u);
}

ll query_sum(int u, int l, int r){
	if(l <= tr[u].l && tr[u].r <= r){
		return tr[u].sum;
	}
	
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	ll sum = 0;
    // 之前此处没赋初值 0 ，栽跟头 * n
	if(l <= mid) sum = query_sum(u << 1, l, r);
	if(r > mid) sum += query_sum(u << 1 | 1, l, r);
	return sum;
}

ll query_A_max(int u, int l, int r){
	if(l <= tr[u].l && tr[u].r <= r) return tr[u].maxa;
	
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	ll res = -1e16;
	if(l <= mid) res = query_A_max(u << 1, l, r);
	if(r > mid) res = Max(res, query_A_max(u << 1 | 1, l, r));
	return res;
}

ll query_B_max(int u, int l, int r){
	if(l <= tr[u].l && tr[u].r <= r) return tr[u].maxb;
	
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	ll res = -1e16;
	if(l <= mid) res = query_B_max(u << 1, l, r);
	if(r > mid) res = Max(res, query_B_max(u << 1 | 1, l, r));
	return res;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	
	build(1, 1, n);
	
	int op, l, r, x;
	while(m--){
		scanf("%d%d%d", &op, &l, &r);
		if(op == 1){
			scanf("%d", &x);
			update_add(1, l, r, x);
		}
		else if(op == 2){
			scanf("%d", &x);
			update_min(1, l, r, x);
		}
		else if(op == 3) printf("%lld\n", query_sum(1, l, r));
		else if(op == 4) printf("%lld\n", query_A_max(1, l, r));
		else printf("%lld\n", query_B_max(1, l, r));
	}
	return 0;
}

温馨提示（给自己）

  • 不开 \(\text{long long}\) 见祖宗
  • 不赋初值见祖宗
  • 写错函数名见祖宗
  • 修改乱序见祖宗

最后，让我们愉快地通过这个水(dú liú)题() 。

\(\text{Updated on 2022.12.20 : }\) 更新了\(\mathcal{线段树的综合应用}\)。

标签：线段,20,int,sum,tr,节点,未完待续,ll,2022.12
From： https://www.cnblogs.com/ZZM-248/p/16994047.html

相关文章

  • 我的2022年-总结、感悟、碎碎念
    我的2022年-总结、感悟、碎碎念 又到年底了，总结下2022吧，今年还是蛮多收获和感悟的，感觉越发活的通透了些，有些事情我们无法把握，有些事情我们能把握。淡然面对无法把握的......
  • 2023年元旦放假安排来了！放假通知模板提前保存到备忘录中
    2023年元旦很快就要如约而至，那么元旦放假吗？放几天假呢？元旦放假安排来了：新的一年元旦放假时间是从2022年的12月31日-2023年的1月2日共三天时间，没有其他调休安排，大家可以利......
  • 32001152纪国强
    你饿我答微信小程序--第十六组一、项目总览1.产品定位面向青年学生群体基于食物评价与用户习惯完成食物推荐2.项目介绍本项目立项之初以解决当下青年......
  • 2022圣诞节手抄报模板怎么高清打印出来？手机在线打印很简单
    2022年圣诞节马上就要到了，有很多中小学生都被英语老师要求画一张圣诞节手抄报，对于比较有画画天赋的人来说，画一张手抄报不是什么难事，但是对于一些不会画画的孩子来说，这就又......
  • 2019 年 stackoverflow 网站最受欢迎的 20 个 Python 问题
    在最新一期的“Python开发者周刊”（Pycoder'sweekly）里，我看到一则有意思的分享，故转出来分享给大家。该分享来自是一份”pythonweeklyreports“，统计了2019年里stackoverf......
  • 我的 2019 年 Python 文章榜单
    现在是2020年的第一天，我相信从昨天开始，各位的信息流里肯定充斥了各式各样的年度盘点/回顾/总结/记录之类的内容。虽然来得稍晚了，但我还是想给诸位送上这一篇文章。我将在......
  • 最新版Photoshop 2023更新 (ps 2023) for Mac 支持M1 v24.0激活版
    Photoshop2023是一款电脑必备修图工具，该版本已经更新到ps2023版！最新的ps2023帮助你组合、修饰和重新混合您的照片，为您的旧黑白添加新颜色，或者让不需要的东西消失，也或者将......
  • 论文推荐｜TDSC2022 安全补丁识别最新的方案E-SPI
    摘要：TDSC2022发表了安全补丁识别最新的方案“EnhancingSecurityPatchIdentificationbyCapturingStructuresinCommits”(E-SPI)。本文分享自华为云社区《【论文......
  • MAUI新生4.1-控件视图：控件总览（未完待续）
    根据控件的功能特点，以及个人的习惯，我将MAUI的控件划分为以下几个大类：Page页面类Layout布局类Content单一内容类Collection集合内容类Form表单类Shape形状类辅助功......
  • 注意！2022年度公司年检开始啦！
    2020年度公司年检正式开始了，您还在愁怎么做吗？不要烦恼，小编为您支招：公司年度检验是指工商行政管理机关依法按年度对公司进行检查，确认公司继续经营资格的法定制度。凡领取《中......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99