segment tree laze propagation

reference :- spoj forum

Lazy Propagation means that you only update what you actually need to, when you need to.
For example, if we have a segment tree that covers the range 1-20.
 If we update segment [1,20], we update only the value of the root node
of the tree and set a flag on it's children [1,10] and [11,20] to let them know that they
need to be updated.

Next, if we query [6,7] then when we reach a node in the traversal that
 has the update flag on, we need to flag it's children and update it's value.

[1,10] is flagged for update
query [6,7]
Traversal Route:
[1,10] - push update flag to [1,5] and [6,10] and update value of [1,10]
[6,10] - push update flag to [6,8] and [9,10] and update value of [6,10]
[6.8] - push update flag to [6,7] and [8,8] and update value of [6,8]
[6,7] - push update flag to [6,6] and [7,7] and update value of [6,7]

This leaves [1,5], [6,6], [7,7], [8,8], [9,10] flagged for update.

Chef and Churu codechef solution for interlinked Segment tree

Chef and Churu

1. #include<stdio.h>
2. #include<algorithm>
3. #include<vector>
4. using namespace std;
5. typedef long long int lli;
6. typedef long int li;
7. li to=0;
8. #define F first
9. #define S second
10. lli arr[100005];
11. lli sum[100005],ran[100005];
13. vector <pair<pair<int,int> ,int> > pa(100005),tre(300005);
14. vector <pair<pair<int,int> ,int> > :: iterator it,it2;
15. //build(1,t,0,t-1);
16. int build(int index, int n, int s,int e )
17. {
18. if(s==e)
19. {
20. tre[index]=pa[s];
21. return 0;
22. }
23. int m=(s+e)/2;
24. build(index*2,n,s,m);
25. build(index*2+1,n,m+1,e);
26. int le=index*2,ri=index*2+1;
27. if(tre[le].first.first<tre[ri].first.first)
28. tre[index].F.F=tre[le].F.F;
29. else tre[index].F.F=tre[ri].F.F;
31. if(tre[le].F.S>tre[ri].F.S)
32. tre[index].F.S=tre[le].F.S;
33. else
34. tre[index].F.S=tre[ri].F.S;
35. }
37. int query(int index,int l,int r,int p,int dif)
38. {
39. if(l==r && tre[index].F.F<=p && tre[index].F.S>=p)
40. {
41. // do the needful
42. ran[tre[index].S]+=dif;
43. return 0;
44. }
45. if(tre[index].F.F<=p && tre[index].F.S>=p)
46. {
47. query(index*2,l,(l+r)/2,p,dif);
48. query(index*2+1,(l+r)/2+1,r,p,dif);
50. }
52. }
54. int main()
55. { // freopen("kr.in", "r", stdin);
56. long long int t;
57. lli a,b,c;
59. scanf("%lld",&t);
60. for(long long int i=0;i<t;i++)
61. {
62. scanf("%lld",&arr[i]);
63. if(i==0)
64. sum[i]=arr[i];
65. else
66. sum[i]=arr[i]+sum[i-1];
67. }
68. for(long long int i=0;i<t;i++)
69. {
70. scanf("%lld %lld",&a,&b);
71. a--,b--;
72. if(a==0)
73. ran[i]=sum[b];
74. else
75. ran[i]=sum[b]-sum[a-1];
76. pa[i]=make_pair(make_pair(a,b),i);
79. }
80. long long int mm;
81. sort(pa.begin(),pa.begin()+t);
82. // build a new seg tree for
83. build(1,t,0,t-1);
84. /* for(int i=1;i<=t*2;i++)
85. {
86. printf("%d %d %d %d \n",i,tre[i].F.F+1,tre[i].F.S+1,tre[i].S);
87. }*/
88. scanf("%lld",&mm);
89. for(long long int i=0;i<mm;i++)
90. {
91. scanf("%lld %lld %lld",&a,&b,&c);
92. if(a==1)//update
93. {b--;
94. to=0;
95. lli dif=c-arr[b];
96. arr[b]=c;
97. //int query(int index,int l,int r,int p,int dif)
98. query(1,0,t-1,b,dif);
101. }
102. else if(a==2)
103. {
104. b--;c--;
105. lli tt=0;
106. for(int i=b;i<=c;i++)
107. {
108. tt+=ran[i];
109. }
110. printf("%lld\n",tt);
111. }
112. }
114. }

The important point is the sort the range segment tree so that we are able to minimize the range will of the parent and we are able to choose the path , so just a overhead of sorting the ranges using pair sort and the creating the range tree we have great optimization for the range segment tree..... Enjoy the new concept.

Segment tree

1. http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html

(the first solutin is buggy) , see the last one

list of good questions  

1.can you answer these queries (gss1) , solu -: https://github.com/VitSalis/SPOJ/blob/master/GSS1/gss1.cpp