线段树基本操作——建树+单点修改+区间查询
保存:
struct tree
{
int l,r;
int data;
}t[N*4];
建树:
void bulid (int p,int l,int r) //线段树建树
{
t[p].l=l,t[p].r=r;
if(l==r) { t[p].data=a[l];return ;}
int mid=(l+r)/2;
bulid(2*p,l,mid);
bulid(2*p+1,mid+1,r);
t[p].data=max(t[2*p].data,t[p*2+1].data);
}
单点修改:
void change(int p,int x,int v)
{
if(t[p].l==t[p].r) { t[p].data=v;return ;}
int mid =(t[p].l+t[p].r)/2;
if(x<=mid) change(p*2,x,v);
else change(2*p+1,x,v);
t[p].data=max(t[p*2].data,t[2*p+1].data);
}
区间查询:以最简单的最大值为例
在找某一个区间的时候,会从大分解到小,最终一般都是有多个不同深度的节点返回多个区间段最大值。
根据当前节点的区间情况分为以下种种:
1.l <= pl <= pr <= r ,这中直接返回当前区间最大值。
2.pl <= l <= pr <=r,分为两种情况:
l>mid,只会递归进入右子树: 例如:区间[1,8]上找[5,8] ,此时有5>4,进入右子树[5,8];
l<=mid,两棵树都会进去,但右子树会立刻返回,比如[1,8]上找[4,8],此时有4>=4,进入右子树后,立刻有1<=5<=8<=8,此时可以直接返回。
3.l<=pl <= r<= pr ,与上述情况类似。
4.pl<=l<=r<=pr,分为两种情况:
(1) l 和 r 都小于mid或者大于mid,只会递归一颗子树。
(2) l 和 r 在mid的两侧,两颗都会递归进去,直到满足第一种情况。
int ask(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r) return t[p].data;
int mid=(t[p].l+t[p].r)/2;
int val=-(1<<30);
if(l<=mid) val=max(val,ask(2*p,l,r));
if(r>mid) val=max(val,ask(2*p+1,l,r));
return val;
}
区间查询的实质就是找线段树上可以组成[l,r]这个区间的所有节点区间。