kartikstud's blog

By kartikstud, history, 2 weeks ago, In English,

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 dataVector = {5, -8, 6, 12, -9};

int small(int x,int y){return min(x,y);}
SegmentTree < int > rangeMinQueries(dataVector,INT_MAX,small);

int sum(int x,int y){return x+y;}
SegmentTree < int > rangeSumQueries(dataVector,0,sum);

long long product(long long x,long long y){return x*y;}
SegmentTree < long long > rangeProductQueries(dataVector,1,product);

also have a look at the following solutions to popular SPOJ segment tree problems:
solution to SPOJ GSS1 using segTree library : https://ideone.com/EFxf6O
solution to SPOJ KGSS using segTree library : https://ideone.com/fUK5Jz

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.
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.

Read more »

  • Vote: I like it
  • +14
  • Vote: I do not like it