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)

@aneee004 @everule1 @ssrivastava990 @ssjgz

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.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
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"...
Reading symbols from ./a.out...done.
(gdb) r < MKTHNUM-testcase-sample.txt 
Starting program: /home/simon/devel/hackerrank/otherpeoples/a.out < MKTHNUM-testcase-sample.txt
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
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 :slight_smile:

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