`
bcyy
  • 浏览: 1819198 次
文章分类
社区版块
存档分类
最新评论

线段树

 
阅读更多

HH神的线段树出神入化，所以跟着HH学习线段树。

风格：

maxn是题目给的最大区间，而节点数要开4倍，确切的说……

lson和rson辨别表示结点的左孩子和右孩子。

PushUp(int rt)是把当前结点的信息更新到父节点

PushDown（int rt)是把当前结点的信息更新给孩子结点。

rt表示当前子树的根（root），也就是当前所在的结点。


思想：

对于每个非叶节点所标示的结点 [a,b]，其做孩子表示的区间是[a,(a+b)/2]，其右孩子表示[(a+b)/2,b].

构造：



离散化和线段树：

题目：x轴上有若干个线段，求线段覆盖的总长度。

普通解法：设置坐标范围[min,max],初始化为0，然后每一段分别染色为1，最后统计1的个数，适用于线段数目少，区间范围小。

离散化的解法：离散化就是一一映射的关系，即将一个大坐标和小坐标进行一一映射，适用于线段数目少，区间范围大。

例如：[10000,22000],[30300,55000],[44000,60000],[55000,60000].

第一步：排序 10000 22000 30300 44000 55000 60000

第二部：编号 1 2 3 4 5 6

第三部：用编号来代替原数，即小数代大数 。

[10000,22000]~[1,2]

[30300,55000]~[3,5]

[44000,60000]~[4,6]

[55000,60000]~[5,6]

然后再用小数进行普通解法的步骤，最后代换回去。

线段树的解法：线段树通过建立线段，将原来染色O(n)的复杂度减小到 log（n），适用于线段数目多，区间范围小的情况。

离散化的线段树：适用于线段数目多，区间范围大的情况。


构造：

动态数据结构：

struct node{

node* left;

node* right;

……

}

静态全局数组模拟（完全二叉树）：

struct node{

int left;

int right;

……

}Tree[MAXN]

例如:



线段树与点树：

线段树的每一个结点表示一个点，成为点树，比如说用于求第k小数的线段树。

点树结构体：

struct node{

int l, r;

int c;//用于存放次结点的值，默认为0

}T[3*MAXN];

创建：

创建顺序为先序遍历，即先构造根节点，再构造左孩子，再构造右孩子。

[cpp] view plaincopyprint?
  1. voidconstruct(intl,intr,intk){
  2. T[k].l=l;
  3. T[k].r=r;
  4. T[k].c=0;
  5. if(l==r)return;
  6. intm=(l+r)>>1;
  7. construct(l,m,k<<1);
  8. construct(m+1,r,(k<<1)+1);
  9. return;
  10. }



[A,B,C]：A表示左值，B表示右值，C表示在静态数组中的位置，由此可知，n个点的话大约共有2*n个结点，因此开3*n的结构体一定是够的。


更新值：

[cpp] view plaincopyprint?
  1. voidinsert(intd,intk){
  2. //如果找到了就c值+1返回。
  3. if(T[k].l==T[k].r&&d==T[k].l){
  4. T[k].c+=1;
  5. return;
  6. }
  7. intm=(T[k].l+T[k].r)>>1;
  8. if(d<=m)insert(d,k<<1);
  9. elseinsert(d,(k<<1)+1);
  10. //更新每一个c，向上更新
  11. T[k].c=T[k<<1].c+T[(k<<1)+1].c;
  12. }

查找值：

[cpp] view plaincopyprint?
  1. //k表示树根，d表示要查找的值
  2. voidsearch(intd,intk,int&ans)
  3. {
  4. if(T[k].l==T[k].r){
  5. ans=T[k].l;
  6. ans=T[k].l;
  7. }
  8. intm=(T[k].l+T[k].r)>>1;
  9. //不懂
  10. if(d>T[(k<<1)].c)search(d-T[k<<1].c,(k<<1)+1,ans);
  11. elsesearch(d,k<<1,ans);
  12. }

search函数的用法不太懂。

例题解：

（待更新）


四类题型：

1.单点更新 只更新叶子结点，然后把信息用PushUp(int r)这个函数更新上来。

hdu1166：敌兵布阵

线段树功能：update：单点替换 query：区间最值




poj2828

树状数组：

[cpp] view plaincopyprint?
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<string>
  4. #include<cstring>
  5. usingnamespacestd;
  7. typedefpair<int,int>PII;
  9. constintmaxn=200000;
  11. intC[maxn+100];
  12. intB[maxn+100];
  13. intn;
  14. PIIarr[maxn+100];
  16. intlowbit(intk){returnk&(-k);}
  18. voidinit(){
  19. for(inti=1;i<=n;i++)C[i]=lowbit(i);
  20. memset(B,-1,n+10);
  21. }
  23. voidupdate(inti){
  24. while(i<=n){
  25. C[i]--;
  26. i+=lowbit(i);
  27. }
  28. }
  31. intquery(inti){
  32. intret=0;
  33. while(i>0){
  34. ret+=C[i];
  35. i-=lowbit(i);
  36. }
  37. returnret;
  38. }
  40. voiddebug(){
  41. for(inti=1;i<=n;i++)cout<<i<<""<<query(i)<<endl;
  42. }
  45. voidfun(inta,intv){
  46. intl=1,r=n;
  47. while(l<r){
  48. intm=(l+r)>>1;
  49. if(query(m)>=a)r=m;
  50. elsel=m+1;
  51. }
  52. //cout<<"here"<<l<<endl;
  53. update(l);
  54. //cout<<"here2"<<endl;
  55. //debug();
  56. B[l]=v;
  57. //returnl;
  58. }
  63. intmain(){
  64. while(~scanf("%d",&n)){
  65. init();
  66. inta,b;
  67. for(inti=1;i<=n;i++){
  68. scanf("%d%d",&a,&b);
  69. a++;
  70. arr[i].first=a;
  71. arr[i].second=b;
  72. }
  73. for(inti=n;i>0;i--)fun(arr[i].first,arr[i].second);
  74. //debug2();
  75. //boolflag=false;
  76. for(inti=1;i<=n;i++){
  77. i==1?printf("%d",B[i]):printf("%d",B[i]);
  78. //if(B[i]!=-1&&!flag){printf("%d",B[i]);flag=true;}
  79. //elseif(B[i]!=-1)printf("%d",B[i]);
  80. }
  81. puts("");
  82. }
  83. return0;
  84. }

poj-3468

[cpp] view plaincopyprint?
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. usingnamespacestd;
  6. #definelsonl,m,rt<<1
  7. #definersonm+1,r,rt<<1|1
  9. typedeflonglongLL;
  11. constintmaxn=111111;
  13. LLcol[maxn<<2];
  14. LLsum[maxn<<2];
  16. voidPushUp(LLrt){
  17. sum[rt]=sum[rt<<1]+sum[rt<<1|1];
  18. }
  20. //pushdown的作用是如果此点可以更新。
  21. //也就是更新到下一层
  22. //如果是底层，那么是不用pushdown的。
  23. voidPushDown(LLrt,LLm){
  24. if(col[rt]){
  25. //col[rt<<1]=col[rt<<1|1]=col[rt];
  26. col[rt<<1]+=col[rt];
  27. col[rt<<1|1]+=col[rt];
  28. sum[rt<<1]+=col[rt]*(m-(m>>1));
  29. sum[rt<<1|1]+=col[rt]*(m>>1);
  30. col[rt]=0;
  31. }
  32. }
  34. voidbuild(LLl,LLr,LLrt){
  35. col[rt]=0;
  36. //cout<<l<<""<<r<<endl;
  37. if(l==r){
  38. scanf("%I64d",&sum[rt]);
  39. //cout<<rt<<""<<sum[rt]<<endl;
  40. return;
  41. }
  42. intm=(l+r)>>1;
  43. build(lson);
  44. build(rson);
  45. PushUp(rt);
  46. }
  48. LLquery(LLL,LLR,LLl,LLr,LLrt){
  49. LLret=0;
  50. if(L<=l&&r<=R){
  51. //if(col[rt])returnsum[rt]+(r-l+1)*col[rt];
  52. returnsum[rt];
  53. }
  54. PushDown(rt,r-l+1);
  55. intm=(l+r)>>1;
  56. if(L<=m)ret+=query(L,R,lson);
  57. if(R>m)ret+=query(L,R,rson);
  58. returnret;
  59. }
  61. voidupdate(LLL,LLR,LLc,LLl,LLr,LLrt){
  62. if(L<=l&&r<=R){
  63. sum[rt]+=c*(r-l+1);
  64. col[rt]+=c;//子节点没有更新
  65. return;
  66. }
  67. PushDown(rt,r-l+1);
  68. intm=(l+r)>>1;
  69. if(L<=m)update(L,R,c,lson);
  70. if(R>m)update(L,R,c,rson);
  71. PushUp(rt);
  72. }
  74. voiddebug(intn){
  75. for(inti=1;i<=(n*3);i++){
  76. cout<<i<<"";
  77. }
  78. cout<<endl;
  79. for(inti=1;i<=(n*3);i++){
  80. cout<<col[i]<<"";
  81. }
  82. cout<<endl<<endl;
  83. for(inti=1;i<=(n*3);i++){
  84. cout<<i<<"";
  85. }
  86. cout<<endl;
  87. for(inti=1;i<=(n*3);i++){
  88. cout<<sum[i]<<"";
  89. }
  90. cout<<endl;
  91. }
  93. intmain(){
  94. LLN,Q;
  95. while(~scanf("%I64d%I64d",&N,&Q)){
  96. //cout<<"N="<<N<<endl;
  97. memset(sum,0,sizeof(sum));
  98. memset(col,0,sizeof(col));
  99. build(1,N,1);
  100. //debug(N);
  101. for(inti=0;i<Q;i++){
  102. charch[3];
  103. LLa,b,c;
  104. scanf("%s",ch);
  105. if(ch[0]=='Q'){
  106. scanf("%I64d%I64d",&a,&b);
  107. printf("%I64d\n",query(a,b,1,N,1));
  108. }
  109. else{
  110. scanf("%I64d%I64d%I64d",&a,&b,&c);
  111. update(a,b,c,1,N,1);
  112. }
  113. //debug(N);
  114. }
  115. }
  116. return0;
  117. }

分享到：
| 特别实用的一些软件强烈推荐！
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    acm程序设计竞赛_培训_线段树

    浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计竞赛_培训_线段树浙江大学_acm程序设计...

    线段树的一种实现

    一种简单的线段树的实现 ，基础功能比较完善

    pascal区间线段树

    一个讲述线段树的好资料，这里主要是程序部分，希望对广大成员能够有所帮助

    几道经典线段树题目及代码

    线段树、线段树啊、线段树，线段树啊、线段树

    线段树模板

    手打了一份线段树代码，用于c++编程， 线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 使用线段树可以快速的查找某一个节点在若干条线段中出现的...

    线段树ppt的好东东

    线段树ppt，线段树ppt，线段树ppt，树ppt，线段树ppt，线段树ppt，

    线段树区间更新code

    线段树区间更新代码线段树区间更新代码线段树区间更新代码线段树区间更新代码

    线段树解析与经典例题.ppt

    一个线段是对应于一个区间的，因此线段树也可以叫做区间树。 线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的...

    权值线段树和主席树入门

    权值线段树和主席树入门PPT，权值线段树，顾名思义就是记录权值的线段树，普通的线段树直接以坐标为l，r建树，而权值线段树是以大小来建树，树上寸的信息是该权值的数量，而通过建树时二分从小到大的性质，可以用这...

    线段树初步（C++）

    讲解线段树基本应用，适合初学者下载使用！

    线段树完整版

    ACM学习中 涉及到线段树的代码分析模板

    线段树六题

    著名的线段树六题 囊括线段树整个知识点， 十分实用 当年凭借此六题， NOIP+NOI秒杀线段树题

    线段树学习ppt

    线段树学习ppt

    线段树模板 zoj1128

    本资源是对线段树操作比较完整的操作，包括线段树的动态插入，动态删除和维护，可以查询区段的最大值，最小值，完成线段树的基本操作。

    线段树PPT两个，所有常规用法

    线段树PPT，所有常规用法线段树PPT，所有常规用法线段树PPT，所有常规用法线段树PPT，所有常规用法

    线段树，针对一组数的的统计十分方便

    线段树，针对一组数的的统计十分方便。 线段树，针对一组数的的统计十分方便。 线段树，针对一组数的的统计十分方便。 线段树，针对一组数的的统计十分方便。 线段树，针对一组数的的统计十分方便。

    线段树.pdf

    线段树完全版，涉及到线段树的所有用法。 包括单点更新（增减，替换），区间求和，区间最值。 区间求最大值的位置。 成段更新（延迟标记，增减）。 离散化 扫描线

    线段树 go语言实现

    go语言实现的线段树源码, 可以直接运行, 代码简洁清晰, 快去下载吧

    线段树高级数据结构实现

    线段树点更新

    线段树(一)

    线段树(一)

Magicbox
Global site tag (gtag.js) - Google Analytics