华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1292|回复: 1
打印 上一主题 下一主题

基本线段树

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2019-11-7 22:36:14 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
线段树是一种常用的数据结构,常常被用于统计区间和,最值等问题,它的基本思想是将区间(l,r)分成(l,m)和(m+1,r)两个基本等长区间,利用和,最大值等的特性(具有一定的传递性)进行统计,这样可以充分利用已经统计的有效信息,减少统计次数。比如整个区间是a1-a10有10个数,我们要多次查询(x,y)区间的数字和问题,我们先建立线段树,用结构体(l,r,s)表示区间(L R)之间的和为S,那么建立线段树如下:
回复

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
沙发
 楼主| 发表于 2019-11-7 22:36:54 | 只看该作者
  1. ///先决条件  位操作 树状数组(?)
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. const int mn=100;

  5. int A[mn]; //原数组
  6. int Sum[mn<<2];//Sum求和,开四倍空间
  7. int Tag[mn<<2];//lazy标记

  8. int n,k,x,y,z;

  9. ///左儿子
  10. int ls(int p){return (p<<1);}
  11. ///右儿子
  12. int rs(int p){return (p<<1|1);}

  13. //PushUp函数更新节点信息,这里是求和
  14. void PushUp(int p){        Sum[p]=Sum[ls(p)]+Sum[rs(p)];}

  15. void f(int l,int r,int p,int k) ///lr区间的数加上k
  16. {
  17.         Tag[p]+=k;
  18.         Sum[p]+=k*(r-l+1);
  19. }

  20. void PushDown(int l,int r,int p)
  21. {
  22.         int m=(l+r)>>1;
  23.         f(l,m,ls(p),Tag[p]);
  24.         f(m+1,r,rs(p),Tag[p]);
  25.         Tag[p]=0;
  26. }

  27. void Update(int L,int R,int k,int l,int r,int p)
  28. {
  29.         if(L<=l && r<=R)
  30.                 {
  31.                         Sum[p]+=k*(r-l+1);
  32.                         Tag[p]+=k;
  33.                         return;
  34.                 }
  35.         PushDown(l,r,p);
  36.         int m=(l+r)>>1;
  37.         if(L<=m) Update(L,R,k,l,m,ls(p));
  38.         if(R>m) Update(L,R,k,m+1,r,rs(p));
  39. }
  40. //Build函数建立线段树
  41. void Build(int l,int r,int p)  //[l,r]表示当前节点区间,p表示当前节点的实际存储位置
  42. {
  43.         if(l==r)  //若到达叶节点
  44.                 {
  45.                         Sum[p]=A[l];//存储A数组的值
  46.                         return;
  47.                 }
  48.         int m=(l+r)>>1;
  49.         Build(l,m,ls(p));
  50.         Build(m+1,r,rs(p));
  51.         //更新信息
  52.         PushUp(p);
  53. }

  54. int Query(int L,int R,int l,int r,int p)
  55. ///[L,R]表示操作区间,[l,r]表示当前区间,p当前节点编号
  56. {
  57.         if(L<=l && r<=R)        return Sum[p];
  58.         int m=(l+r)>>1;
  59.         int ANS=0;
  60.         if(L<=m) ANS+=Query(L,R,l,m,ls(p));
  61.         if(R>m) ANS+=Query(L,R,m+1,r,rs(p));
  62.         return ANS;
  63. }

  64. int  main()
  65. {
  66.         n=20;
  67.         for (int i=1; i<=20; i++) A[i]=9+i;  ///假设20个数字是10-29
  68.         Build(1,n,1);
  69.         cin>>k; ///进行k次区间修改
  70.         while (k--)
  71.                 {
  72.                         cin>>x>>y>>z; ///xy区间加上z
  73.                         Update(x,y,z,1,n,1); ///
  74.                         cout<<Query(x,y,1,n,1);///输出区间和
  75.                 }
  76.         return 0;
  77. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 02:05 , Processed in 0.116621 second(s), 22 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表