Creating segment for sqrt decomposition
int segment[10000];
int preprocess(int input[], int n) {
int current_segment = -1;
int segment_size = sqrt(n);
for (int i=0; i<n; i++) {
if (i % segment_size == 0) {
current_segment++; //new segment
}
segment[current_segment] += input[i];
}
return segment_size;
}