Help Me Rectifying My Mistake (MKTHNUM) (Rectified)

I am trying to do this problem using Persistent Segment Tree.

Please help me figure out why does my code give a Runtime error, and how to rectify it.

``````cur->right = prev->right; //code gives RE on this statement
``````
My Solution
``````//https://www.spoj.com/problems/MKTHNUM/
#include <bits/stdc++.h>
using namespace std;

const long long N = 1e5 + 10;
long long a[N];
map<long long, long long> Sorted;

struct Node {
Node *left, *right;
long long val;

Node(Node* l, Node* r, int v) {
left = l;
right = r;
val = v;
}
};

Node *Versions[N];

void Build(Node *cur, long long l, long long r) {
cur->val = 0;
if(l == r)
return;
cur->left = new Node(NULL, NULL, 0);
cur->right = new Node(NULL, NULL, 0);
long long mid = (l + r) / 2;
Build(cur->left, l, mid);
Build(cur->right, mid + 1, r);
}

void Insert(Node *prev, Node *cur, long long l, long long r, long long pos) {
if(l == r) {
cur->val = 1;
return;
}
long long mid = (l + r) / 2;
if(pos <= mid) {
cur->right = prev->right;
cur->left = new Node(NULL, NULL, 0);
Insert(prev->left, cur->left, l, mid, pos);
}
else {
cur->left = prev->left;
cur->right = new Node(NULL, NULL, 0);
Insert(prev->right, cur->right, mid + 1, r, pos);
}
cur->val = cur->right->val + cur->left->val;
}

long long Query(Node *Left, Node *Right, long long k, long long l, long long r) {
if(l == r)
return Sorted[l];
long long mid = (l + r) / 2;
if(Right->left->val - Left->left->val < k) {
return Query(Left->right, Right->right, k - (Right->left->val - Left->left->val), mid + 1, r);
}
else {
return Query(Left->left, Right->left, k, l, mid);
}
}

void Solve() {
long long n, q;
cin >> n >> q;
for(long long i = 1; i <= n; i++) {
cin >> a[i];
Sorted[a[i]] = i;
}
Node *root = new Node(NULL, NULL, 0);
Versions[0] = root;
Build(Versions[0], 1, n);
for(long long i = 1; i <= n; i++) {
Insert(Versions[i - 1], Versions[i], 1, n, Sorted[a[i]]);
}
for(long long i = 1; i <= q; i++) {
long long ql, qr, k;
cin >> ql >> qr >> k;
cout << Query(Versions[ql - 1], Versions[qr], k, 1, n) << endl;
}
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Solve();
return 0;
}

``````

What does my code do before the RE:

• Takes a as the input array, and the map Sorted sorts it and stores it in the pair [a[i], i] (value, index)
• The value of a position x in the ith version of the Segment tree is the count of the number of elements encountered in the range of position x (i.e [l, r] or the bounds of position x)

Please explain why is my code giving an RE on the following line, and how to rectify the mistake.

``````cur->right = prev->right;
``````

What test input is causing it to crash?

In the example input, my code wasnâ€™t giving any output.
After outputting random stuff, I got to know that there is an error on that line.

Example Input:

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

``````[simon@simon-laptop][14:38:30]
[~/devel/hackerrank/otherpeoples]>cat MKTHNUM-testcase-sample.txt
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
[simon@simon-laptop][14:38:32]
[~/devel/hackerrank/otherpeoples]>gdb ./a.out
GNU gdb (Ubuntu 8.1-0ubuntu3.2) 8.1.0.20180409-git
Copyright (C) 2018 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
(gdb) r < MKTHNUM-testcase-sample.txt
Starting program: /home/simon/devel/hackerrank/otherpeoples/a.out < MKTHNUM-testcase-sample.txt
aryan12-MKTHNUM.cpp:40:14: runtime error: member access within null pointer of type 'Node'

Program received signal SIGSEGV, Segmentation fault.
0x000000000042b5c7 in Insert (prev=0x12d80c0, cur=0x0, l=1, r=7, pos=1) at aryan12-MKTHNUM.cpp:40
40              cur->right = prev->right;
(gdb) quit
``````

`cur` is NULL.

2 Likes

Ohh, now I understood the mistake. Thanks for figuring it out.

And could you please share some of those debugging tricks as you debug so fast.

2 Likes

Just used the flags here and ran it through gdb

2 Likes

I forgot to add the following line before calling the function

``````Versions[i] = Versions[i - 1];
``````

Thus `Versions[i]` was `NULL`

1 Like