526互联

线段树笔记

发布时间 2023-12-31 17:51:24作者: CQWYB

例\(1\)

题目描述

给定一个长为\(n\)的序列，有\(m\)次操作，每次操作为以下三种之一。

  • 修改序列中的一个数
  • 求序列中某连续一段所有数的两两乘积的和\(\text{mod} 1000000007\)。
  • 求序列中某连续一段所有相邻两数乘积的和\(\text{mod} 1000000007\)。

做法

一般单点修改的难点都在于区间合并信息的操作。

\(\text{Part}1\)

先考虑第二个操作，假设对于一个区间我们已经求出了它左右两个子区间的两两乘积之和，例如左区间的数为\(a,b,c\)，我们右区间的数为\(d,e\)，我们已经知道了\(a\times b,a\times c,b\times c\)的和与\(d \times e\)的和。

那合并后增加的部分就为\(a \times d+a\times e+b\times d+b\times e+c\times d+c\times e\)的和，提取公因式得\(a\times(d+e)+b\times(d+e)+c\times(d+e)\)，再提取公因式得\((a+b+c)\times(d+e)\)，我们发现\(a+b+c\)与\(d+e\)都是维护区间的和，可以在线段树合并时维护区间和就可以了。

具体操作为我们对于每个区间维护两个信息，一个为这个区间的两两元素乘积之和\(ans_2\)，另一个为这个区间所有元素的和\(sum\)。

例如在合并\(A\)与\(B\)区间到\(C\)时，可以这么合并：\(C.ans_2=A.ans_2+B.ans_2+A.sum\times B.sum\)，\(C.sum=A.sum+B.sum\)。

\(\text{Part} 2\)

再考虑第一个操作，仿照第二个操作的做法，假设对于一个区间我们已经求出了它左右两个子区间的相邻两数乘积之和，例如左区间的数为\(a,b,c\)，我们右区间的数为\(d,e\)，我们已经知道了\(a\times b,b\times c\)的和与\(d \times e\)的和。

那合并后增加的部分就为\(c\times d\)，我们发现\(c\)与\(d\)区间的左右元素，可以在线段树合并时维护左右元素是谁就可以了。

具体操作为我们对于每个区间维护三个信息，一个为这个区间的两两元素乘积之和\(ans_1\)，另一个为这个区间最左边元素为\(l\)，最右边元素为\(r\)。

例如在合并\(A\)与\(B\)区间到\(C\)时，可以这么合并：\(C.ans_1=A.ans_1+B.ans_1+A.r\times B.l\)，\(C.l=A.l,C.r=B.r\)。

这道题启发我们往往不能只维护题目所求的信息（因为这样很有可能无法直接维护）还要维护一些其它的信息。

例\(2\) 小白逛公园

题目传送门

做法

在例\(1\)的引导下，我们可以考虑一个区间的答案可以由左右两个区间的答案更新而来，也可以是左右两个区间的最大子段和，也就是左区间的后缀最大和再加上右区间的前缀最大和。而一个区间的前缀最大和可以是由它的左区间的前缀最大和更新过来，也可使左区间加上右区间的前缀最大和更新过来，右区间同理。所以我们还要维护区间和的信息。

\(Code\)

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+50;
int a[N],n,m;
struct data{
	int sum,leftmax,rightmax,totalmax;
}tree[N*4];
data merge(data A,data B){
	data C;
	C.sum=A.sum+B.sum;
	C.leftmax=max(A.leftmax,A.sum+B.leftmax);
	C.rightmax=max(B.rightmax,B.sum+A.rightmax);
	C.totalmax=max(max(A.totalmax,B.totalmax),A.rightmax+B.leftmax);
	return C;
}
void build(int p,int l,int r){
	if(l==r){
		tree[p].sum=tree[p].leftmax=tree[p].rightmax=tree[p].totalmax=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);build(p*2+1,mid+1,r);
	tree[p]=merge(tree[p*2],tree[p*2+1]);
	return;
}
void modify(int p,int l,int r,int x,int y){
	if(l==r){
		tree[p].sum=y;
		tree[p].leftmax=y;
		tree[p].rightmax=y;
		tree[p].totalmax=y;
		return;
	}
	else{
		int mid=(l+r)/2;
		if(x>mid) modify(p*2+1,mid+1,r,x,y);
		else modify(p*2,l,mid,x,y);
		tree[p]=merge(tree[p*2],tree[p*2+1]);
	}
}
data query(int p,int l,int r,int x,int y){
	if(l>=x&&r<=y){
		return tree[p];
	}
	int mid=(l+r)/2;
	if(y<=mid)return query(p*2,l,mid,x,y);
	else if(x>mid)return query(p*2+1,mid+1,r,x,y);
	else{
		data A=query(p*2,l,mid,x,mid);
		data B=query(p*2+1,mid+1,r,mid+1,y);
		data C;
		
		C.sum=A.sum+B.sum;
		C.leftmax=max(A.leftmax,A.sum+B.leftmax);
		C.rightmax=max(B.rightmax,B.sum+A.rightmax);
		C.totalmax=max(max(A.totalmax,B.totalmax),A.rightmax+B.leftmax);
		return C;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(a==1){
			if(b>c)swap(b,c);
			printf("%d\n",query(1,1,n,b,c).totalmax);
		}
		else{
			modify(1,1,n,b,c);
		}
	}
	return 0;
}