Persistent Segment Tree help needed — implementation giving TLE with pointers, AC without pointers

help
, , ,
1

I’m solving this problem on Codechef: https://www.codechef.com/problems/PSHTTR

This problem can be solved online with persistent segment tree (can also be solved offline without persistence), but my solution is giving TLE when I implement it using pointers. Is there any reason why pointers may be significantly slower?? I get AC without pointers in 0.63s but TLE with a time limit of 1.5s.

Here is my implementation using pointers: https://www.codechef.com/viewsolution/17104558
And implementation without pointers: https://www.codechef.com/viewsolution/17104790

Here is the crux of my implementation using pointers. Its simple point updates and range xor queries:

Note: This is a dynamic persistent segment tree, i.e memory of my tree is not predefined but index of element can be in range of 1 to 1e9. I’m assigning new nodes whenever I find nullptr in left or right positions. Maybe I’m doing something wrong here, or maybe this itself is a very slow method. Any ideas how to speed this up, or is there a better method? I don’t know much about pointers so please forgive me :stuck_out_tongue:

struct node {
    int val;
    node *left, *right;
    node (int v, node* l, node* r) {
        val = v;
        left = l;
        right = r;
    }
};
#define null new node (0, NULL, NULL);

node *version[maxn];

void update(node *prev, node *curr, int L, int R, int idx, int val) {
    curr->val = prev->val;
    if (L == R) {
        assert(idx == L);
        curr->val ^= val;
    }
    else {
        if (prev->left == nullptr) prev->left = null;
        if (prev->right == nullptr) prev->right = null;
        int mid = (L+R)/2;
        if (idx <= mid) {
            curr->right = prev->right;
            curr->left = null;
            update(prev->left, curr->left, L, mid, idx, val);
        }
        else {
            curr->left = prev->left;
            curr->right = null;
            update(prev->right, curr->right, mid+1, R, idx, val);
        }
        curr->val = curr->left->val ^ curr->right->val;
    }
}

int query (node *curr, int L, int R, int li, int ri) {
    if (curr == nullptr || ri < L || li > R)
        return 0;
    if (li <= L && ri >= R)
        return curr->val;
    int mid = (L+R)/2;
    return query(curr->left, L, mid, li, ri) ^ query(curr->right, mid+1, R, li, ri);
}

Crux of my implementation using a buffer array, without pointers:

struct node {
    int val;
    int left, right;
    node() : val(0), left(0), right(0) {}
    node(int val) : val(val), left(0), right(0) {}
    node(int val, int l, int r) : val(val), left(l), right(r) {}
};
 
node stree[35*maxn];
int root[maxn], nodeCnt = 0;
 
void update(int old, int &curr, int L, int R, int idx, int val) {
    curr = ++nodeCnt;
    stree[curr] = stree[old];
    if (L == R) {
        assert(idx == L);
        stree[curr].val ^= val;
    }
    else {
        int mid = (L+R)/2;
        if (idx <= mid) {
            update(stree[old].left, stree[curr].left, L, mid, idx, val);
        }
        else {
            update(stree[old].right, stree[curr].right, mid+1, R, idx, val);
        }
        stree[curr].val = stree[stree[curr].left].val ^ stree[stree[curr].right].val;
    }
}
 
int query (int curr, int L, int R, int li, int ri) {
    if (curr == 0 || ri < L || li > R)
        return 0;
    if (li <= L && ri >= R)
        return stree[curr].val;
    int mid = (L+R)/2;
    return query(stree[curr].left, L, mid, li, ri) ^ query(stree[curr].right, mid+1, R, li, ri);
}

Help would be much appreciated!

2

Your implementation seems to be logically correct, so let’s talk optimizations.

if (prev->left == nullptr) prev->left = null;
if (prev->right == nullptr) prev->right = null;

Here you are creating a bunch of new “null” nodes that you don’t even need. When creating a path from root to leaf in the new version you’re also creating the same path but with null nodes in the previous version, which is unnecessary.
It is possible to come up with a way around this, but I think the way your second solution handles this is most elegant. In this solution stree[0] is the null node. It has left and right set to 0, which means both child pointers refer to itself. This effectively forms an infinite tree of null nodes at the cost of only 1 node. So the solution is efficient and with minimum extra code.

I think not making unnecessary nodes should be enough to get an AC. Also, if you want to use pointers, nothing restricts you to using dynamic memory only. In the second solution you can replace integer indices with pointers, and it should work just as well.

2 Likes
3

Yeah, this makes sense. Thanks a lot!

4

I got AC after added these two lines:
version[1]->right = version[1];
version[1]->left = version[1];

and removed:
if (prev->left == nullptr) prev->left = null;
if (prev->right == nullptr) prev->right = null;

Still, weirdly it was almost twice as slow as my second solution, running in 1.15s. I wonder why O.o

5

Really late reply, but that’s because of dynamic vs static memory allocation for the nodes.