[关闭]
@zzzc18 2017-06-23T09:37:22.000000Z 字数 1679 阅读 650

线段树模板

线段树


就是个模板

orz几乎一遍写不对

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #define MAXN 100009
  5. #define LL long long
  6. LL a[MAXN];
  7. LL n,m;
  8. class Segment_Tree{
  9. private:
  10. LL cnt;
  11. struct T{
  12. LL ls,rs,left_range,right_range,sum,lazy;
  13. };
  14. T tree[MAXN<<1];
  15. LL seglen(LL x){
  16. return tree[x].right_range-tree[x].left_range+1;
  17. }
  18. void update(LL x){
  19. tree[x].sum=tree[tree[x].ls].sum+tree[tree[x].rs].sum;
  20. }
  21. void pushdown(LL x){
  22. if(tree[x].lazy){
  23. if(tree[x].ls){
  24. tree[tree[x].ls].lazy+=tree[x].lazy;
  25. tree[tree[x].ls].sum+=tree[x].lazy*seglen(tree[x].ls);
  26. }
  27. if(tree[x].rs){
  28. tree[tree[x].rs].lazy+=tree[x].lazy;
  29. tree[tree[x].rs].sum+=tree[x].lazy*seglen(tree[x].rs);
  30. }
  31. }
  32. tree[x].lazy=0;
  33. }
  34. public:
  35. LL Build(LL l,LL r){
  36. LL now=++cnt;
  37. tree[now].left_range=l;tree[now].right_range=r;
  38. if(l==r){
  39. tree[now].sum=a[l];
  40. return now;
  41. }
  42. LL mid=(l+r)>>1;
  43. tree[now].ls=Build(l,mid);
  44. tree[now].rs=Build(mid+1,r);
  45. update(now);
  46. return now;
  47. }
  48. void addnum(LL now,const LL &l,const LL &r,const LL &v){
  49. pushdown(now);
  50. if(l<=tree[now].left_range && tree[now].right_range<=r){
  51. tree[now].sum+=v*seglen(now);
  52. tree[now].lazy+=v;
  53. return;
  54. }
  55. LL mid=(tree[now].left_range+tree[now].right_range)>>1;
  56. if(l<=mid) addnum(tree[now].ls,l,r,v);
  57. if(r>=mid+1) addnum(tree[now].rs,l,r,v);
  58. update(now);
  59. }
  60. LL r2n(LL now,const LL &l,const LL &r){
  61. pushdown(now);
  62. if(l<=tree[now].left_range && tree[now].right_range<=r){
  63. return tree[now].sum;
  64. }
  65. LL mid=(tree[now].left_range+tree[now].right_range)>>1;
  66. LL re=0;
  67. if(l<=mid) re+=r2n(tree[now].ls,l,r);
  68. if(r>=mid+1) re+=r2n(tree[now].rs,l,r);
  69. update(now);
  70. return re;
  71. }
  72. }Seg;
  73. int main(){
  74. scanf("%lld%lld",&n,&m);
  75. LL i;
  76. for(i=1;i<=n;i++)
  77. scanf("%lld",&a[i]);
  78. Seg.Build(1,n);
  79. for(i=1;i<=m;i++){
  80. LL opt,l,r,x;
  81. scanf("%lld%lld%lld",&opt,&l,&r);
  82. if(opt==1){
  83. scanf("%lld",&x);
  84. Seg.addnum(1,l,r,x);
  85. }
  86. else
  87. printf("%lld\n",Seg.r2n(1,l,r));
  88. }
  89. return 0;
  90. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注