kartik8800's blog

(Not So)General Purpose Segment Tree library
By kartik8800, history, 4 years 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.

UPD: made a video explaining the usage and features https://youtu.be/K-86mKNAsmU

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kartik8800 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Consider this problem:

Given an array A of size N and a constant B, process the following queries:

  1. Update the value at position i to x

  2. Given l, r, report the value of Sum{i in [l, r)}( A[i] * B^(i-l) )

Second query asks you to print the hash value of the interval(there are a few problems using this). This can easily be done with point update segtree but it requires you to pass the size of the left interval to your merge function.

Some other problems might require you to know the exact position of the interval for the merge operation. So if you want the fully generalized version, you gotta pass the exact positions of the intervals you're merging. It's easy to see that the right end of the left interval is always adjacent to the left end of the right interval, so it's enough to pass three positions. Here's an implementation of it (iterative).

For lazy propagation, you need three functions instead of one. Recall that each nodes of the segtree store two information:

(1) Lazy
You need to apply Lazy to child nodes
(2) Query
What is the answer when you query the interval represented by this node ignoring the lazy updates from its parent?

Now you need three functions to maintain these definitions.

(1) Apply_To_Lazy(L_target, L_update, target_l, target_r, update_l, update_r)
What is the resulting Lazy value if you apply L_update representing the interval [update_l, update_r) to L_target representing the subinterval [target_l, target_r)?
(2) Merge(Q_l, Q_r, l, m, r)
What is the resulting Query value if you merge two intervals [l, m) and [m, r) with query value Q_l and Q_r respectively? (This part is the same as the point update segtree)
(3) Apply_To_Query(Q_target, L_update, target_l, target_r, update_l, update_r)
What is the resulting Query value if you apply L_update representing the interval [update_l, update_r) to Q_target representing the subinterval [target_l, target_r)?

Recursive; Iterative; Dynamic; These are the implementations, tho not the cleanest, so feel free to make it cleaner. I've recently used the first version on the most recent ABC Problem F.

Of course, passing all these information is very costly. So you might have to erase unnecessary arguments to pass within the TL on some problems.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hey thanks a lot for sharing the info! I am totally aware my implementation is nowhere close to general(should probably update the title), wrote the code long back after learning segment tree(from youtube videos).

    Will try to generalize it further(or maybe rewrite) when I get more time. The only pro I feel is that it is quite easy to use.

    BTW you have some nice implementations for the same, why don't you consider writing a blog and sharing how to use them.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Mostly laziness. Also, I made those for my personal use, not for educational purpose, so people might find it hard to read.

      → Reply