[关闭]
@lychee123 2017-08-14T17:15:16.000000Z 字数 1785 阅读 2956

线段树(区间更新,区间求和)

数据结构


POJ-3468:A Simple Problem with Integers

  1. #include<stdio.h>
  2. #define LL long long
  3. #define MAXN 100010
  4. LL a[MAXN],l,r,i,j,n,m,ans,x;
  5. char b[11];
  6. struct node
  7. {
  8. LL l,r,sum,lazy;
  9. }tr[MAXN*4];
  10. void build(LL id,LL l,LL r)//根,左,右
  11. {
  12. tr[id].l=l;
  13. tr[id].r=r;
  14. tr[id].lazy=0;//延迟标记初始化为0
  15. if(l==r)
  16. tr[id].sum=a[l];
  17. else
  18. {
  19. LL mid=(l+r)/2;
  20. build(id*2,l,mid);//左子树
  21. build(id*2+1,mid+1,r);//右子树
  22. tr[id].sum=tr[id*2].sum+tr[id*2+1].sum;
  23. }
  24. }
  25. void pushdown(LL id)//更新下层区间的值
  26. {
  27. tr[id*2].lazy+=tr[id].lazy;//左子树标记累加
  28. tr[id*2+1].lazy+=tr[id].lazy;//右子树标记累加
  29. tr[id*2].sum+=tr[id].lazy*(tr[id*2].r-tr[id*2].l+1);//区间长度乘以当前标记
  30. tr[id*2+1].sum+=tr[id].lazy*(tr[id*2+1].r-tr[id*2+1].l+1);
  31. tr[id].lazy=0;//标记传递后清空为0
  32. }
  33. void update(LL id,LL l,LL r,LL x)//x为需要更新的值
  34. {
  35. if(l<=tr[id].l&&r>=tr[id].r)//要找的那个区间去包含自己分的区间
  36. {
  37. tr[id].lazy+=x;
  38. tr[id].sum+=x*(tr[id].r-tr[id].l+1);
  39. return;
  40. }
  41. LL mid=(tr[id].l+tr[id].r)/2;
  42. if(r<=mid)
  43. update(id*2,l,r,x);//往左更新
  44. else if(l>mid)
  45. update(id*2+1,l,r,x);//往右更新
  46. else//左右都更新
  47. {
  48. update(id*2,l,r,x);
  49. update(id*2+1,l,r,x);
  50. }
  51. tr[id].sum=tr[id*2].sum+tr[id*2+1].sum;//更新现结点的值
  52. }
  53. void query(LL id,LL l,LL r)//查询函数
  54. {
  55. if(l<=tr[id].l&&r>=tr[id].r)
  56. {
  57. ans+=tr[id].sum;
  58. return;
  59. }
  60. if(tr[id].lazy!=0)
  61. pushdown(id);
  62. LL mid=(tr[id].l+tr[id].r)/2;
  63. if(r<=mid)
  64. query(id*2,l,r);
  65. else if(l>mid)
  66. query(id*2+1,l,r);
  67. else
  68. {
  69. query(id*2,l,mid);
  70. query(id*2+1,mid+1,r);
  71. }
  72. }
  73. int main()
  74. {
  75. scanf("%lld%lld",&n,&m);
  76. for(i=1;i<=n;i++)
  77. scanf("%lld",&a[i]);
  78. build(1,1,n);
  79. while(m--)
  80. {
  81. scanf("%s",b);
  82. if(b[0]=='Q')
  83. {
  84. ans=0;
  85. scanf("%lld%lld",&l,&r);
  86. query(1,l,r);
  87. printf("%lld\n",ans);
  88. }
  89. if(b[0]=='C')
  90. {
  91. scanf("%lld%lld%lld",&l,&r,&x);
  92. update(1,l,r,x);
  93. }
  94. }
  95. return 0;
  96. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注