AcWing 245. 你能回答这些问题吗

线段树不是一个算法，而是一个对区间进行修改、维护的工具。

AcWing 245. 你能回答这些问题吗

题目大意：

给定长度为$N$的数列$A$，以及$M$条指令，每条指令可能是以下两种之一：

1. 1 x y，查询区间$[x,y]$中的最大连续子段和，即\underset{x \le l\le r\le y}{max} \{ \underset{i=l} {\stackrel{r} \sum}A[i] \}。
2. 2 x y，把$A[x]$ 改成 $y$。

对于每个查询指令，输出一个整数表示答案。

思路：

$$ans = max\{ tl的最大字段和，tr的最大字段和，跨域区间中点的最大字段和 \}$$

$tl，tr$分为别左右两个子区间，而$tl和tr$的最大字段和递归来求。

跨越中点的最大字段和 = 以$tl$右端点为右边界向左的最大字段和 + 以$tr$左端点为左边界向右的最大字段和

因此线段树结点要维护四个信息：

• $lmax$:左端点起的向右的最大字段和
• $rmax$:右端点起的向左的最大字段和
• $tmax$:整个区间的最大字段和
• $sum$:区间和

Code:

struct node{
	int l,r;
	int sum,lmax,rmax,tmax;
}tr[N*4];

void pushup(node &u,node &l,node &r){
	u.sum = l.sum + r.sum;
	u.lmax = max(l.lmax,l.sum + r.lmax);
	u.rmax = max(r.rmax,r.sum + l.rmax);
	u.tmax = max(max(l.tmax,r.tmax),l.rmax + r.lmax);
}

void pushup(int u){
	pushup(tr[u],tr[u << 1],tr[u << 1|1]);
}

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

void modify(int u,int x,int v){
	if (tr[u].l == x && tr[u].r == x)	tr[u] = {x,x,v,v,v,v};
	else{
		int mid = tr[u].l + tr[u].r >> 1;
		if (x <= mid)	modify(u << 1,x,v);
		else modify(u << 1|1,x,v);
		pushup(u);
	}
}

node query(int u,int l,int r){
	if (tr[u].l >= l && tr[u].r <= r)	return tr[u];
	else{
		int mid = tr[u].l + tr[u].r >> 1;
		if (r <= mid)	return query(u << 1,l,r);
		else if (l > mid)	return query(u << 1|1,l,r);
		else{
			auto left = query(u << 1,l,r);
			auto right = query(u << 1|1,l,r);
			node res;
			pushup(res,left,right);
			return res;
		}
	}
}

void solve()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i ++)	cin >> w[i];
	build(1,1,n);
	int k,x,y;
	while(m --){
		cin >> k >> x >> y;
		if (k == 1){
			if (x > y)	swap(x,y);
			cout << query(1,x,y).tmax << '\n';
		}else
			modify(1,x,y);
	}
}