[关闭]
@zzzc18 2017-11-09T03:44:37.000000Z 字数 1641 阅读 401

简单线段树

模板库


地址
区间加,区间求和

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