• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Dynamic Segment tree RaFiN_  Apr 22nd, 2019 102 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.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top