I have been recently working on preparing libraries for commonly used data structures in competitive programming.↵
↵
here is a link to the code : https://github.com/kartik8800/segTree↵
↵
The above segment tree library should (according to me) work for a huge number of range query problems with point updates.↵
↵
The things you need to specify to declare a segment tree is a function combine that tells the tree how to combine the results of child nodes to form parent node, an array for which the tree is to be constructed and a value such that combine(x, value) = x.↵
↵
Here are a few examples:↵
↵
vector<int> dataVector = {5, -8, 6, 12, -9};↵
↵
int small(int x,int y){return min(x,y);} <br>↵
SegmentTree < int > rangeMinQueries(dataVector,INT_MAX,small); <br>↵
↵
int sum(int x,int y){return x+y;}<br>↵
SegmentTree < int > rangeSumQueries(dataVector,0,sum);<br>↵
↵
long long product(long long x,long long y){return x*y;}<br>↵
SegmentTree < long long > rangeProductQueries(dataVector,1,product);<br>↵
↵
also have a look at the following solutions to popular SPOJ segment tree problems:<br>↵
solution to SPOJ GSS1 using segTree library : https://ideone.com/EFxf6O<br>↵
solution to SPOJ KGSS using segTree library : https://ideone.com/fUK5Jz<br>↵
↵
I wonder if it is possible to provide a similar implementation of the segtree with lazy propagation, would be amazing to receive help with that.<br>↵
It would be great to know if people find this helpful and also check out implementations of other commonly used data structures like tries, DSU, minQueue and more.↵
↵
<b>UPD:</b> made a video explaining the usage and features [https://youtu.be/K-86mKNAsmU](https://youtu.be/K-86mKNAsmU)
↵
here is a link to the code : https://github.com/kartik8800/segTree↵
↵
The above segment tree library should (according to me) work for a huge number of range query problems with point updates.↵
↵
The things you need to specify to declare a segment tree is a function combine that tells the tree how to combine the results of child nodes to form parent node, an array for which the tree is to be constructed and a value such that combine(x, value) = x.↵
↵
Here are a few examples:↵
↵
vector<int> dataVector = {5, -8, 6, 12, -9};↵
↵
int small(int x,int y){return min(x,y);} <br>↵
SegmentTree < int > rangeMinQueries(dataVector,INT_MAX,small); <br>↵
↵
int sum(int x,int y){return x+y;}<br>↵
SegmentTree < int > rangeSumQueries(dataVector,0,sum);<br>↵
↵
long long product(long long x,long long y){return x*y;}<br>↵
SegmentTree < long long > rangeProductQueries(dataVector,1,product);<br>↵
↵
also have a look at the following solutions to popular SPOJ segment tree problems:<br>↵
solution to SPOJ GSS1 using segTree library : https://ideone.com/EFxf6O<br>↵
solution to SPOJ KGSS using segTree library : https://ideone.com/fUK5Jz<br>↵
↵
I wonder if it is possible to provide a similar implementation of the segtree with lazy propagation, would be amazing to receive help with that.<br>↵
It would be great to know if people find this helpful and also check out implementations of other commonly used data structures like tries, DSU, minQueue and more.↵
↵
<b>UPD:</b> made a video explaining the usage and features [https://youtu.be/K-86mKNAsmU](https://youtu.be/K-86mKNAsmU)
