线段树

区间修改，查询 $logn$
总复杂度 $nlogn$
高级数据结构
可以用于88满足区间二分和区间加法的高级数据结构

求和
最大公因数
最大最小值
区间覆盖问题

区间修改区间查询
分为以下几个部分

建树
区间修改
区间查询
懒标记下移

建树

void build(int id,int l,int r){
	if(l==r){ segtree[id]=a[l]; return ; }
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	push_up(id);
}

区间修改

void quadd(int li,int ri,int id,int l,int r,int v){
	if(li<=l&&r<=ri){
		lazy[id]+=v;
		segtree[id]+=(r-l+1)*v;
		return ; 
	}
	push_down(id,l,r);
	int mid=(l+r)>>1;
	if(mid>=li){ quadd(li,ri,id<<1,l,mid,v);}
	if(mid<ri){ quadd(li,ri,id<<1|1,mid+1,r,v);}
	push_up(id);
}

注意懒标记下移，边界判断

区间查询

int query(int li,int ri,int id,int l,int r){
	if(li<=l&&r<=ri){
		return segtree[id];
	}
	push_down(id,l,r);
	int sum=0;
	int mid=(l+r)>>1;
	if(mid>=li){ sum+=query(li,ri,id<<1,l,mid);}
	if(mid<ri){ sum+=query(li,ri,id<<1|1,mid+1,r);}
	return sum;
}

懒标记下移

void push_down(int id,int l,int r){
	int mid=(l+r)>>1;
	segtree[id<<1]+=(mid-l+1)*lazy[id];
	segtree[id<<1|1]+=(r-mid)*lazy[id];
	lazy[id<<1]+=lazy[id];
	lazy[id<<1|1]+=lazy[id];
	lazy[id]=0;
}

注意懒标记下推时的范围大小

模板

贴一波完整代码

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int n,m;
long long segtree[400001];
int a[100001];
int lazy[400001];
void push_up(int id){
	segtree[id]=segtree[id<<1]+segtree[id<<1|1];
}
void push_down(int id,int l,int r){
	int mid=(l+r)>>1;
	segtree[id<<1]+=(mid-l+1)*lazy[id];
	segtree[id<<1|1]+=(r-mid)*lazy[id];
	lazy[id<<1]+=lazy[id];
	lazy[id<<1|1]+=lazy[id];
	lazy[id]=0;
}
void build(int id,int l,int r){
	if(l==r){ segtree[id]=a[l]; return ;}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	push_up(id);
}
void quadd(int li,int ri,int id,int l,int r,int v){
	if(li<=l&&r<=ri){
		segtree[id]+=(r-l+1)*v;
		lazy[id]+=v;
		return ; 
	}
	push_down(id,l,r);
	int mid=(l+r)>>1;
	if(mid>=li){ quadd(li,ri,id<<1,l,mid,v);}
	if(mid<ri){ quadd(li,ri,id<<1|1,mid+1,r,v);}
	push_up(id);
}
long long query(int li,int ri,int id,int l,int r){
	if(li<=l&&r<=ri){
		return segtree[id];
	}
	push_down(id,l,r);
	long long sum=0;
	int mid=(l+r)>>1;
	if(mid>=li){ sum+=query(li,ri,id<<1,l,mid);}
	if(mid<ri){ sum+=query(li,ri,id<<1|1,mid+1,r);}
	return sum;
}
int main()
{
	cin>>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 id,x,y,k;
		scanf("%d",&id);
		if(id==1){
			scanf("%d%d%d",&x,&y,&k);
			quadd(x,y,1,1,n,k); 
		}else{
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(x,y,1,1,n));
		}
	}
	return 0;
}

区间覆盖问题

[NOI2015]软件包管理器

将所有的+=改为=
考虑线段的初始值以及更改后的值如何变化
考虑懒标记的变化

区间最大值问题

[ZJOI2008]树的统计

注意懒标记和最大值线段树的初始化为负无穷

区间连续字段的长最长长度

序列操作

一道极其疯狂的线段树码农题
维护：
一个节点中最长的1段长度，最长的0段长度
右段开始的1段长度，右端开始的0段长度
左端开始的1段长度，左端开始的0段长度
在push_down ，push_up ,合并查询最长1段数时都有许多细节需要思考

建树