SHARE
TWEET

Dynamic Segment tree

RaFiN_ Apr 22nd, 2019 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. int n,q;
  3.  
  4. struct node{
  5.     node *left,*right;
  6.     ll lazy,sum;
  7.     node(){
  8.         left = right = NULL;
  9.         lazy = sum = 0;
  10.     }
  11. }*root;
  12.  
  13. ll Sum(ll l,ll r){
  14.     return (r*(r+1))/2 - (l*(l-1))/2;
  15. }
  16.  
  17. void checkLazy(node *curr,ll b,ll e){
  18.         if(curr->lazy!=0){
  19.         if(b!=e){
  20.             int mid = (b+e)>>1;
  21.             if(!curr->left)curr->left = new node();
  22.             if(!curr->right)curr->right = new node();
  23.             curr->left->sum-=(curr->lazy*(ll)(mid-b+1));
  24.             curr->right->sum-=(curr->lazy*(ll)(e-mid));
  25.             curr->left->lazy+=curr->lazy;
  26.             curr->right->lazy+=curr->lazy;
  27.         }
  28.         curr->lazy = 0;
  29.     }
  30. }
  31.  
  32. void update(node *curr,ll b,ll e,ll l,ll r,ll val){
  33.     checkLazy(curr,b,e);
  34.     if(l>e||b>r)return ;
  35.     if(b>=l&&e<=r){
  36.         curr->sum-=(val*(ll)(e-b+1));
  37.         curr->lazy+=val;
  38.         return ;
  39.     }
  40.     if(!curr->left)curr->left = new node();
  41.     if(!curr->right)curr->right = new node();
  42.     int mid = (b+e)>>1;
  43.     update(curr->left,b,mid,l,r,val);
  44.     update(curr->right,mid+1,e,l,r,val);
  45.     curr->sum = curr->left->sum + curr->right->sum;
  46. }
  47.  
  48. ll query(node *curr,ll b,ll e,ll l,ll r){
  49.     checkLazy(curr,b,e);
  50.     if(b>r||l>e)return 0;
  51.     if(b>=l&&e<=r)return curr->sum;
  52.     if(!curr->left)curr->left = new node();
  53.     if(!curr->right)curr->right = new node();
  54.     int mid = (b+e)>>1;
  55.     ll p1 = query(curr->left,b,mid,l,r);
  56.     ll p2 = query(curr->right,mid+1,e,l,r);
  57.     return p1 + p2;
  58. }
  59.  
  60.  
  61. int main()
  62. {
  63.     ///booster()
  64.     ///read("input.txt");
  65.     scani2(n,q);
  66.     root = new node();
  67.     while(q--){
  68.         int c,l,r;
  69.         scani3(c,l,r);
  70.         if(c==1){
  71.             int v;
  72.             scani(v);
  73.             update(root,1,MAX,l,r,v);
  74.         }
  75.         else printf("%lld\n",Sum(l,r) + query(root,1,MAX,l,r));
  76.     }
  77.  
  78.     return 0;
  79. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top