线段树入门
把我csdn的blog搬过来的（（将就看
线段树
想学主席树，然后开了一篇题解，看到“学习可持久化线段树之前一定要学懂线段树”这句话我只好把线段树又学了一遍（（
这块从昨天到今天学了四个小时，做了三页纸笔记，所以有错的可能性不大（但是wtcl，所以还是有很大可能的
概括
线段树的理解，按照书上的（（
- 线段树的每个节点都代表一个区间；
- 线段树具有唯一的根节点，代表的区间是整个统计范围；
- 线段树的每个叶节点都代表一个长度为1的元区间[x,x]；
- 对于每个内部节点[l,r]，它的左子节点是[l,mid]，右子节点是[mid+1,r]，其中mid=(l+r)/2;
图我就不放了
另一个点就是”父子2倍“，即节点i的权值=左儿子权值+右儿子的权值,举个栗子，节点i的权值编号p，左儿子权值即p*2，右儿子权值即p * 2+1（应该没说错吧；
建树
先讲一下线段树的建树。
struct数组存储我就先略过了；
上代码：
void build (int p,int l,int r) {
t[p].l=l,t[p].r=r; //节点p代表区间[l,r];
if (l==r){
t[p].dat=a[l];
return; //叶节点;
}
int mid=(l+r)/2; //折半(根据“父子二倍”,求mid;
build(p*2,l,mid); //构造左子节点，即[l,mid],编号p*2;
build(p*2+1,mid+1,r); //同上一步，构造右子节点，即[mid+1,r],编号p*2+1;
t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
//从下往上传递信息;
}
build (1,1,n); //调用入口;
单点修改
所谓单点修改，就是：
- 从根节点出发，递归找到代表区间[x,x]的叶节点；
- 更新（从下往上）[x,x]以及其所有祖先节点上的信息；
- 时间复杂度为O(logN);
上代码：
void change (int p,int x,int v) {
if (t[p].l==t[p].r) {
t[p].dat=v;
return; //找叶节点;
}
int mid=(t[p].l+t[p].r)/2; //折半;
if (x<=mid) //找x所属的区间;
change(p*2,x,v);
else
change(p*2+1,x,v);
t[p].dat=max(t[p*2].dat,t[p*2+1],dat);
}
change(1,x,v); //调用入口;
区间查询
递归：
- [l,r]完全覆盖了当前节点代表的区间，回溯，该节点的dat值为候选答案；
- 左子节点与[l,r]有重叠部分，递归访问左子节点；
- 右子节点与[l,r]有重叠部分，递归访问右子节点；
代码：
int ask(int p,int l,int r) {
if (l<=t[p].l &&r>=t[p].r) return t[p].dat; //完全包含;
int mid=(t[p].l+t[p].r)/2;
int val=a(1<<30);
if (l<=mid) val=max(val,ask(p*2,l,r)); //与左子节点有重叠;
if (r>mid) val=max(val,ask(p*2+1,l,r)); //与右子节点有重叠;
return val;
}
cout<<ask(1,l,r)<<endl; //调用入口;
还有两个点，即区间修改&延迟标记；
区间修改就是结合单点修改和区间查询…
延迟标记是“在回溯前向节点p加一个标记，标识“该节点曾被修改，但子节点尚未更新””。
这边就不敲代码了（（我太菜了怕出错
总结
有点虎头蛇尾，毕竟是自己对线段树的总结可能会有误；
本篇blog应该适用于线段树入门QAQ
谢谢大家耐心看完awa
