General Purpose Segment Tree library
Разница между en1 и en2, 123 символ(ов) изменены
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)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский kartik8800 2020-08-31 15:12:08 8
en2 Английский kartik8800 2020-08-31 11:53:49 123
en1 Английский kartik8800 2019-11-02 14:48:35 1597 Initial revision (published)