线段树是一种树形结构，它将数据序列划分为若干个线段，每个线段包含若干个数据元素。

线段树主要用于高效处理‌区间查询和更新‌问题，其核心作用包括：

快速区间查询 通过预处理数据，可在对数时间复杂度（O(logN)）内查询区间内元素的出现次数或统计信息（如最大值、最小值、总和等）。 ‌

高效区间更新 支持对区间内元素值进行修改，并通过懒标记等技术减少重复计算，优化更新操作的效率。 ‌

空间优化需求 未优化的线段树空间复杂度为2N，实际应用中通常需要4N的数组空间以避免越界，有时需配合离散化进一步压缩空间。 ‌

T2

题目给出了2个操作

1. 查询$[x,y]$中最大连续子段和
2. 将$a_x$改为$y$

由与这道题涉及到了区间求和和单点修改,所有考虑用线段树

怎样在线段树中维护区间最大连续子段和呢? 类比用分治求最大连续子段和

1. 求左子区间的最大子段和
2. 求右子区间的最大子段和
3. 求包含$mid$的最大子段和

其中最难的是3,3可以表是为左子区间的最大后缀和加上右子区间的最大前缀和

$x_1$为左子区间的最大后缀和的下标 $x_2$为右子区间的最大前缀和的下标

#include<iostream>
using namespace std;
const int N=5e5+10;
int n,m;
struct D{
	int l,r;
	int ts,ls,rs,sum;
}tr[4*N];
int a[N];
void pushup(D &x,D &l,D &r){
	x.sum=l.sum+r.sum;
	x.ts=max(max(l.ts,r.ts),l.rs+r.ls);
	x.ls=max(l.ls,l.sum+r.ls);
	x.rs=max(r.rs,r.sum+l.rs);
}

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

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

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


D query(int l,int r,int k){
	int x=tr[k].l,y=tr[k].r;
	if(l<=x&&y<=r){
		return tr[k];
	}
	int mid=(x+y)>>1;
	
	if(r<=mid) return query(l,r,k<<1);
	else if(l>mid) return query(l,r,k<<1|1);
	else{
		D lp=query(l,r,k<<1),rp=query(l,r,k<<1|1),res;
		pushup(res,lp,rp);
		return res;
	}
}
int main(){
  cin>>n>>m;
  
  int op;
  int x,y;
  for(int i=1;i<=n;i++) cin>>a[i];
  build(1,n,1);
  for(int i=1;i<=m;i++){
  	cin>>op>>x>>y;
    if(op==1) {
    cout<<query(min(x,y),max(x,y),1).ts<<endl;
	}
    else{
    modify(x,y,1);
	}
  }
  return 0;
}

T5

题目大意就是给出$N$个矩形求总面积(重复的只计算一遍)

这道题需要用到扫描线

扫描线：假设有一条扫描线从一个图形的下方扫向上方（或者左方扫到右方），那么通过分析扫描线被图形截得的线段就能获得所要的结果。该过程可以用线段树进行加速。 如图,图中有4个矩形,我们从左至右进行扫描,碰到竖线就标记 如下图 我们可以定义每个矩形左边的权值为1,右边为-1

然后把所有的竖边按照x坐标升序排序。这样，对于每个矩形，扫描线总是会先碰到左边，然后再碰到右边。那么就能保证扫描线所截的长度永远非负了。

这样操作以后，就可以和线段树扯上关系。先把所有端点在y轴上离散化（其实就是把所有点的纵坐标存到Y[]里，然后升序排个序，最后去重）。

建立一棵线段树，其每个端点维护一条线段（也就是一个区间）的信息：

1. 该线段被覆盖了多少次（被多少个矩形所覆盖）。
2. 该线段内被整个图形所截的长度是多少。

显然，只要一条线段被覆盖，那么它肯定被图形所截。所以，整个问题就转化为了一个区间查询问题，即：每次将 当前扫描线扫到的边 对应的信息 按照之前赋上的权值更新，然后再查询线段树根节点的信息，最后得到当前扫描线扫过的面积。这就可以用线段树来实现了

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+20;
int n;
vector<double> ys;
struct node {
	double x, yl, yr;
	int k;
	bool operator< (const node &t)const {
		return x < t.x;
	}
} sg[N * 2];
struct tree {
	int l, r;
	int cnt;
	double len;
} t[N * 8];
int find(double x) {
	return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}
void pushup(int u) {
	if (t[u].cnt) {
		t[u].len = ys[t[u].r + 1] - ys[t[u].l];
	} else if (t[u].l != t[u].r) {
		t[u].len = t[u << 1].len + t[u << 1 | 1].len;
	} else {
		t[u].len = 0;
	}
}
void build(int u, int l, int r) {
	if (l == r) {
		t[u] = {l, r, 0, 0};
	} else {
		t[u] = {l, r};
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
	}
}
void change(int u, int l, int r, int k) {
	if (t[u].l >= l && t[u].r <= r) {
		t[u].cnt += k;
		pushup(u);
	} else {
		int mid = t[u].l + t[u].r >> 1;

		if (l <= mid) {
			change(u << 1, l, r, k);
		}

		if (r > mid) {
			change(u << 1 | 1, l, r, k);
		}

		pushup(u);
	}
}
int main() {
	int T = 1;

	while (cin >> n && n) {
		ys.clear();

		for (int i = 1, j = 0; i <= n; i++) {
			double x, xx, y, yy;
			cin >> x >> y >> xx >> yy;
			sg[j++] = {x, y, yy, 1};
			sg[j++] = {xx, y, yy, -1};
			ys.push_back(y);
			ys.push_back(yy);
		}

		sort(ys.begin(), ys.end());
		ys.erase(unique(ys.begin(), ys.end()), ys.end());

		build(1, 0, ys.size() - 2);
		sort(sg, sg + n * 2);
		double ans = 0;

		for (int i = 0; i < n * 2; i++) {
			if (i > 0) {
				ans += t[1].len * (sg[i].x - sg[i - 1].x);
			}

			change(1, find(sg[i].yl), find(sg[i].yr) - 1, sg[i].k);
		}

		cout << "Test case #" << T++ << endl;
		cout << "Total explored area: " << fixed << setprecision(2) << ans << endl;
		cout << endl;
	}

	return 0;
}