官方网站内容更新需要怎么做,超好看WordPress,wordpress用户系统插件,环保主题的网站模板浅谈线段树 数据结构——线段树 O、引例 A.给出n个数#xff0c;n100#xff0c;和m个询问#xff0c;每次询问区间[l#xff0c;r]的和#xff0c;并输出。 一种回答#xff1a;这也太简单了#xff0c;O#xff08;n#xff09;枚举搜索就行了。 另一种回答n100和m个询问每次询问区间[lr]的和并输出。 一种回答这也太简单了On枚举搜索就行了。 另一种回答还用得着o(n枚举前缀和o(1)就搞定。 那好我再修改一下题目。 B.给出n个数n100和m个操作每个操作可能有两种1、在某个位置加上一个数2、询问区间[lr]的和并输出。 回答on枚举。 动态修改最起码不能用静态的前缀和做了。 好我再修改题目 C.给出n个数n1000000和m个操作每个操作可能有两种1、在某个位置加上一个数2、询问区间[lr]的和并输出。 回答on枚举绝对超时。 再改 D给出n个数n1000000和m个操作每个操作修改一段连续区间[a,b]的值 回答从a枚举到b一个一个改。。。。。。有点儿常识的人都知道超时 那怎么办这就需要一种强大的数据结构线段树。 一、基本概念 1、线段树是一棵二叉搜索树它储存的是一个区间的信息。 2、每个节点以结构体的方式存储结构体包含以下几个信息 区间左端点、右端点这两者必有 这个区间要维护的信息事实际情况而定数目不等。 3、线段树的基本思想二分。 4、线段树一般结构如图所示 5、特殊性质 由上图可得 1、每个节点的左孩子区间范围为[lmid]右孩子为[mid1,r] 2、对于结点k左孩子结点为2*k右孩子为2*k1这符合完全二叉树的性质 二、线段树的基础操作 注以下基础操作均以引例中的求和为例结构体以此为例 struct node{ int l,r,w;//lr分别表示区间左右端点w表示区间和}tree[4*n1]; 线段树的基础操作主要有5个 建树、单点查询、单点修改、区间查询、区间修改。 1、建树即建立一棵线段树 ① 主体思路a、对于二分到的每一个结点给它的左右端点确定范围。 b、如果是叶子节点存储要维护的信息。 c、状态合并。 ②代码 void build(int l,int r,int k)
{tree[k].ll;tree[k].rr;if(lr)//叶子节点 {scanf(%d,tree[k].w);return ; }int m(lr)/2;build(l,m,k*2);//左孩子 build(m1,r,k*21);//右孩子 tree[k].wtree[k*2].wtree[k*21].w;//状态合并此结点的w两个孩子的w之和
} ③注意 a.结构体要开4倍空间为啥自己画一个[1,10]的线段树就懂了 b.千万不要漏了return语句因为到了叶子节点不需要再继续递归了。 2、单点查询即查询一个点的状态设待查询点为x ①主体思路与二分查询法基本一致如果当前枚举的点左右端点相等即叶子节点就是目标节点。如果不是因为这是二分法,所以设查询位置为x当前结点区间范围为了lr中点为 mid则如果xmid则递归它的左孩子否则递归它的右孩子 ②代码 void ask(int k)
{if(tree[k].ltree[k].r) //当前结点的左右端点相等是叶子节点是最终答案 {anstree[k].w;return ;}int m(tree[k].ltree[k].r)/2;if(xm) ask(k*2);//目标位置比中点靠左就递归左孩子 else ask(k*21);//反之递归右孩子
} ③正确性分析 因为如果不是目标位置由if—else语句对目标位置定位逐步缩小目标范围最后一定能只到达目标叶子节点。 3、单点修改即更改某一个点的状态。用引例中的例子对第x个数加上y ①主体思路 结合单点查询的原理找到x的位置根据建树状态合并的原理修改每个结点的状态。 ②代码 void add(int k)
{if(tree[k].ltree[k].r)//找到目标位置 {tree[k].wy;return;}int m(tree[k].ltree[k].r)/2;if(xm) add(k*2);else add(k*21);tree[k].wtree[k*2].wtree[k*21].w;//所有包含结点k的结点状态更新
} 4、区间查询即查询一段区间的状态在引例中为查询区间[x,y]的和 ①主体思路 mid(lr)/2 ymid ,即 查询区间全在当前区间的左子区间往左孩子走 xmid 即 查询区间全在当前区间的右子区间往右孩子走 否则两个子区间都走 ②代码 void sum(int k)
{if(tree[k].lxtree[k].ry) {anstree[k].w;return;}int m(tree[k].ltree[k].r)/2;if(xm) sum(k*2);if(ym) sum(k*21);
} ③正确性分析 情况13不用说对于情况2最差情况是搜到叶子节点此时一定满足情况1 5、区间修改即修改一段连续区间的值我们已给区间[a,b]的每个数都加x为例讲解 Ⅰ.引子 有人可能就想到了 修改的时候只修改对查询有用的点。 对这就是区间修改的关键思路。 为了实现这个我们引入一个新的状态——懒标记。 Ⅱ 懒标记 懒标记比较难理解我尽力讲明白。。。。。。 1、直观理解“懒”标记懒嘛用到它才动不用它就睡觉。 2、作用存储到这个节点的修改信息暂时不把修改信息传到子节点。就像家长扣零花钱你用的时候才给你不用不给你。 3、实现思路重点 a.原结构体中增加新的变量存储这个懒标记。 b.递归到这个节点时只更新这个节点的状态并把当前的更改值累积到标记中。注意是累积可以这样理解过年很多个亲戚都给你压岁钱但你暂时不用所以都被你父母扣下了。 c.什么时候才用到这个懒标记当需要递归这个节点的子节点时标记下传给子节点。这里不必管用哪个子节点两个都传下去。就像你如果还有妹妹父母给你们零花钱时总不能偏心吧 d.下传操作 3部分①当前节点的懒标记累积到子节点的懒标记中。 ②修改子节点状态。在引例中就是原状态子节点区间点的个数*父节点传下来的懒标记。 这就有疑问了既然父节点都把标记传下来了为什么还要乘父节点的懒标记乘自己的不行吗 因为自己的标记可能是父节点多次传下来的累积每次都乘自己的懒标记造成重复累积 ③父节点懒标记清0。这个懒标记已经传下去了不清0后面再用这个懒标记时会重复下传。就像你父母给了你5元钱你不能说因为前几次给了你10元钱, 所以这次给了你15元那你不就亏大了。 懒标记下穿代码f为懒标记其余变量与前面含义一致。 void down(int k)
{tree[k*2].ftree[k].f;tree[k*21].ftree[k].f;tree[k*2].wtree[k].f*(tree[k*2].r-tree[k*2].l1);tree[k*21].wtree[k].f*(tree[k*21].r-tree[k*21].l1);tree[k].f0;
} Ⅲ 完整的区间修改代码 void add(int k)
{if(tree[k].latree[k].rb)//当前区间全部对要修改的区间有用 {tree[k].w(tree[k].r-tree[k].l1)*x;//(r-1)1区间点的总数tree[k].fx;return;}if(tree[k].f) down(k);//懒标记下传。只有不满足上面的if条件才执行所以一定会用到当前节点的子节点 int m(tree[k].ltree[k].r)/2;if(am) add(k*2);if(bm) add(k*21);tree[k].wtree[k*2].wtree[k*21].w;//更改区间状态
} Ⅳ.懒标记的引入对其他基本操作的影响 因为引入了懒标记很多用不着的更改状态存了起来这就会对区间查询、单点查询造成一定的影响。 所以在使用了懒标记的程序中单点查询、区间查询也要像区间修改那样对用得到的懒标记下传。其实就是加上一句if(tree[k].f) downk其余不变。 2017.5.16 之前写的单点修改不需要下传懒标记在此订正单点修改也需要下传懒标记 引入了懒标记的单点查询代码 void ask(int k)//单点查询
{if(tree[k].ltree[k].r){anstree[k].w;return ;}if(tree[k].f) down(k);//懒标记下传唯一需要更改的地方int m(tree[k].ltree[k].r)/2;if(xm) ask(k*2);else ask(k*21);
} 引入了懒标记的区间查询代码 void sum(int k)//区间查询
{if(tree[k].lxtree[k].ry) {anstree[k].w;return;}if(tree[k].f) down(k)//懒标记下传唯一需要更改的地方int m(tree[k].ltree[k].r)/2;if(xm) sum(k*2);if(ym) sum(k*21);
} 三、总结 线段树5种基本操作代码 #includecstdio
using namespace std;
int n,p,a,b,m,x,y,ans;
struct node
{int l,r,w,f;
}tree[400001];
inline void build(int k,int ll,int rr)//建树
{tree[k].lll,tree[k].rrr;if(tree[k].ltree[k].r){scanf(%d,tree[k].w);return;}int m(llrr)/2;build(k*2,ll,m);build(k*21,m1,rr);tree[k].wtree[k*2].wtree[k*21].w;
}
inline void down(int k)//标记下传
{tree[k*2].ftree[k].f;tree[k*21].ftree[k].f;tree[k*2].wtree[k].f*(tree[k*2].r-tree[k*2].l1);tree[k*21].wtree[k].f*(tree[k*21].r-tree[k*21].l1);tree[k].f0;
}
inline void ask_point(int k)//单点查询
{if(tree[k].ltree[k].r){anstree[k].w;return ;}if(tree[k].f) down(k);int m(tree[k].ltree[k].r)/2;if(xm) ask_point(k*2);else ask_point(k*21);
}
inline void change_point(int k)//单点修改
{if(tree[k].ltree[k].r){tree[k].wy;return;}if(tree[k].f) down(k);int m(tree[k].ltree[k].r)/2;if(xm) change_point(k*2);else change_point(k*21);tree[k].wtree[k*2].wtree[k*21].w;
}
inline void ask_interval(int k)//区间查询
{if(tree[k].latree[k].rb) {anstree[k].w;return;}if(tree[k].f) down(k);int m(tree[k].ltree[k].r)/2;if(am) ask_interval(k*2);if(bm) ask_interval(k*21);
}
inline void change_interval(int k)//区间修改
{if(tree[k].latree[k].rb){tree[k].w(tree[k].r-tree[k].l1)*y;tree[k].fy;return;}if(tree[k].f) down(k);int m(tree[k].ltree[k].r)/2;if(am) change_interval(k*2);if(bm) change_interval(k*21);tree[k].wtree[k*2].wtree[k*21].w;
}
int main()
{scanf(%d,n);//n个节点 build(1,1,n);//建树 scanf(%d,m);//m种操作 for(int i1;im;i){scanf(%d,p);ans0;if(p1){scanf(%d,x);ask_point(1);//单点查询,输出第x个数 printf(%d,ans);} else if(p2){scanf(%d%d,x,y);change_point(1);//单点修改 }else if(p3){scanf(%d%d,a,b);//区间查询 ask_interval(1);printf(%d\n,ans);}else{scanf(%d%d%d,a,b,y);//区间修改 change_interval(1);}}
} 四、空间优化 父节点k左二子2*k右儿子2*k1需要4*n的空间 但并不是所有的叶子节点占用到2n1——4n 这就造成大量空间浪费 2*n空间表示法推荐博客http://www.cppblog.com/MatoNo1/archive/2015/05/05/195857.html 用dfs序表示做节点下标 父节点k左儿子k1右儿子k左儿子区间长度*2不是父节点下标父节点区间长度。因为当树不满时两者不相等 具体实现这里就不再写模板了就是改改左右儿子的下标 可参考代码 题目楼房重建http://www.cnblogs.com/TheRoadToTheGold/p/6361242.html 里面的建树用的2*n空间 五、模板题 1、codevs 1080 线段树练习 单点修改区间查询 http://codevs.cn/problem/1080/ View Code 2、codevs 1081 线段树练习2 单点查询区间修改 http://codevs.cn/problem/1081/ View Code 3、codevs 1082 线段树练习3 区间修改区间查询 View Code 六、经典例题 codevs 3981/SPOJ GSS1/GSS3 ——区间最大子段和 Bzoj3813 奇数国——区间内某个值是否出现过洛谷 P2894 酒店 Hotel ——区间连续一段空的长度 codevs 2421 /Bzoj1858 序列操作——多种操作 codevs 2000 / BZOJ 2957: 楼房重建——区间的最长上升子序列 Codevs3044 矩形面积求并——扫描线 作者xxy 出处http://www.cnblogs.com/TheRoadToTheGold/ 本文版权归作者和博客园共有欢迎转载但未经作者同意必须保留此段声明且在文章页面明显位置给出原文连接否则保留追究法律责任的权利。 转载于:https://www.cnblogs.com/rmy020718/p/8832889.html
