线段树
- 基本概念
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。
来自百度百科
- 实现原理
每个节点代表一个区间，在对线段操作的线段树中，每个点代表一条线段，在用线段树维护数列信息的时候，每个点代表一个数，但本质上都是每个点代表一个数。
从这个很丑的图可以看出：维护的还是最小的儿子节点
1、每个节点的左孩子区间范围为[l，mid]，右孩子为[mid+1,r]
2、对于结点k，左孩子结点为2k，右孩子为2k+1，这符合完全二叉树的性质
模板代码
从PPT上复制总结下来的
- 定义线段树
struct Node{
int left, right;
…
}node[MAXN*4];
//一般开到四倍 即MAXN<<=2;
- 建树 Build
即初始化树
#define L(u) (u<<1)//左孩子 即u*2
#define R(u) (u<<1|1)//右孩子 即u*2+1
void Build (int u,int left,int right){ //u表当前结点
//left right 表左区间范围[left,right]
node[u].l = left,node[u].r = right;
......... //结点信息的初始化
if (node[u].l == node[u].r){//到叶结点 return
.........//某些赋值
return ;
}
int mid = (node[u].l + node[u].r)>>1;
Build (L(u),left,mid);
Build (R(u),mid+1,right);
Pushup(u);
}
- 向上回溯 Pushup
该函数就是由子结点递归回来 修改父结点中的信息
void Pushup(int u){
node[u].sum = node[L(u)].sum + node[R(u)].sum;//价值
…….
…… return ;
}
- 延时更新 Pushdown
调用此函数时，结点中一般有个状态标志位 用来判断是否需要往下更新，可以防TLE 只在查询的时候修改
void Pushdown (int u) {//延迟覆盖操作
if (node[u].state == -1) {
//更新父结点，左右子结点信息 }
else if (node[u].state == 1){
//更新父结点，左右子结点信息
}
else {
………
}
}
- 更新修改操作 Update
点的修改
void Update(int L,int C,int l,int r,int rt){//l,r表示当前节点区间，rt表示当前节点编号
if(l==r){//到叶节点，修改
Sum[rt]+=C;
return;
}
int m=(l+r)>>1;
//根据条件判断往左子树调用还是往右
if(L <= m) Update(L,C,l,m,rt<<1);
else Update(L,C,m+1,r,rt<<1|1);
PushUp(rt);//子节点更新了，所以本节点也需要更新信息
}
区间的修改
void Update(int L,int R,int C,int l,int r,int rt){//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号
if(L <= l && r <= R){//如果本区间完全在操作区间[L,R]以内
Sum[rt]+=C*(r-l+1);//更新数字和，向上保持正确
Add[rt]+=C;//增加Add标记，表示本区间的Sum正确，子区间的Sum仍需要根据Add的值来调整
return ;
}
int m=(l+r)>>1;
PushDown(rt,m-l+1,r-m);//下推标记
//这里判断左右子树跟[L,R]有无交集，有交集才递归
if(L <= m) Update(L,R,C,l,m,rt<<1);
if(R > m) Update(L,R,C,m+1,r,rt<<1|1);
PushUp(rt);//更新本节点信息
}
以上都以求和为例
- 查询操作 Query
Data Query(int u,int left,int right)
{
if (left <= node[u].l&&node[u].r <= right)
return node[u].sum;
Pushdown(u);//延迟更新
int mid = (node[u].l + node[u].r)>>1;
if (right <= mid) return Query(L(u),left,right);
else if (left > mid) return Query(R(u),left,right);
else return (Query(L(u),left,mid) + Query(R(u),mid+1,right));
Pushup(u);
}
练习
1.EXAM 1711 http://exam.upc.edu.cn/problem.php?id=1711
维护的应该是区间的最小值，很容易T，需要输入挂,延迟更新应该没有用到，然后其实这道题正解不是线段树，但是可以用用线段树的思想：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+7;
int minn[maxn<<2],add[maxn<<2],s[maxn];
#define l(u) (u<<1)
#define r(u) (u<<1|1)
inline bool scan_d(int &num)
{
char in;
bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<'0'||in>'9')) in=getchar();
if(in=='-')
{
IsN=true;
num=0;
}
else num=in-'0';
while(in=getchar(),in>='0'&&in<='9')
{
num*=10,num+=in-'0';
}
if(IsN) num=-num;
return true;
}
struct node
{
int l,r;
} t[maxn<<2];
void pushup(int u)//向上更新区间最小值
{
minn[u]=min(minn[l(u)],minn[r(u)]);
}
void pushdown(int u)
{
minn[u]-=add[u];
add[l(u)]+=add[u];
add[r(u)]+=add[u];
add[u]=0;
}
void build(int u,int l,int r)
{
t[u].l=l,t[u].r=r;
if(l==r)
{
minn[u]=s[l];
return;
}
if(l>r) return;
int mid=(l+r)>>1;
build(l(u),l,mid);
build(r(u),mid+1,r);
pushup(u);
}
void update(int u,int al,int ar,int x)
{
if(add[u])pushdown(u);//如果u区间还没有处理
if(al<=t[u].l&&t[u].r<=ar)
{
add[u]=x;
pushdown(u);
return;
}
if(al>t[u].r||ar<t[u].l)return;
update(l(u),al,ar,x);
update(r(u),al,ar,x);
pushup(u);
}
int main()
{
int flag=0;
int n,m;
scan_d(n);
scan_d(m);
for(int i=1; i<=n; i++) scan_d(s[i]);
build(1,1,n);
int d,x,y;
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&d,&x,&y);
update(1,x,y,d);
if(minn[1]<0&&!flag)
{
printf("-1
");
flag=i;
}
}
printf("%d
",flag);
return 0;
}