I was given this challenge in a programming "class". Eventually I decided to go for the "Binary Indexed Trees" solution, as data structures are a thing I'd like to know more about. Implementing BIT was somewhat straight forward, things after that - not so much. I ran into "Fatal Signal 11" when uploading the solution to the server, which, from what I've read, is somewhat similar to a Null pointer exception. Couldn't figure out the problem, decided to check out other solutions with BIT but stumbled upon the same problem.
#include<iostream>
using namespace std;
/* <BLACK MAGIC COPIED FROM geeksforgeeks.org> */
int getSum(int BITree[], int index){
int sum = 0;
while (index > 0){
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
void updateBIT(int BITree[], int n, int index, int val){
while (index <= n){
BITree[index] += val;
index += index & (-index);
}
}
/* <BLACK MAGIC COPIED FROM geeksforgeeks.org> */
int Count(int arr[], int x){
int sum = 0;
int biggest = 0;
for (int i=0; i<x; i++) {
if (biggest < arr[i]) biggest = arr[i];
}
int bit[biggest+1];
for (int i=1; i<=biggest; i++) bit[i] = 0;
for (int i=x-1; i>=0; i--)
{
sum += getSum(bit, arr[i]-1);
updateBIT(bit, biggest, arr[i], 1);
}
return sum;
}
int main(){
int x;
cin >> x;
int *arr = new int[x];
for (int temp = 0; temp < x; temp++) cin >> arr[temp];
/*sizeof(arr) / sizeof(arr[0]); <-- someone suggested this,
but it doesn't change anything from what I can tell*/
cout << Count(arr,x);
delete [] arr;
return 0;
}
I am quite stumped on this. It could be just some simple thing I'm missing, but I really don't know. Any help is much appreciated!
You have condition that every number lies between 1 and 1018. So, your biggest number can be 1018. This is too much for the following line:
int bit[biggest+1];