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 :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!

asked
**22 Jan '18, 13:07**

3★sinbycos

33●2

accept rate:
0%