Persistence Made Simple - Tutorial

tutorial
, ,
41

SPOJ set the time limit really strict for KQUERY, they specifically wanted offline solution for that with a faster data structure (e.g. fenwick). That’s why they created KQUERYO as a separate online problem.

2 Likes
42

I assume you did DQUERY by sorting queries by right endpoint? Then you can do the same technique using persistent tree. Same technique, but during build you store the tree at index R as tree[R]. You can now solve queries online, just call tree[R].range_query(L, R)

For KQUERY, the TLE is strict there so only offline works (cuz SPOJ)… but there’s an online counterpart KQUERYO, you can solve that with persistent

43

Bookmarked!! :-)))))

1 Like
44

Awesome tutorial dude! when I start to read about persistent segment tree I didn’t understand the tutorial but this tutorial is a gem and very informative. Good Job!

45

There should be the line
flag[p] = 0;
at 6-th line of newlazykid() function.

int newlazykid(int node, int delta, int L, int R) {
    int p = ++NODES;
    l[p] = l[node];
    r[p] = r[node];
    flag[p] = flag[node]; // need this since lazy kid might be lazy before
    hasflag[p] = true;
    flag[p] = 0;
    
    /* range increase */
    flag[p] += delta;
    st[p] = st[node] + (R - L + 1) * delta;
    /* edit depending on the problem */
    
    return p;
}