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

Правка en2, от SinByCos, 2018-01-21 23:14:20

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, and 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 :P

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!

Теги #help, persistent segment tree, pointers, range xor

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский SinByCos 2018-01-21 23:16:43 49
en3 Английский SinByCos 2018-01-21 23:14:41 7
en2 Английский SinByCos 2018-01-21 23:14:20 0 (published)
en1 Английский SinByCos 2018-01-21 23:13:55 3682 Initial revision (saved to drafts)