Segment Tree | C++ | Sum range in an array

main.cpp

#include <iostream>
#include <cmath>
using namespace std;
int getMid(int x, int y){
	return((x+y)/2);
}
int segTreeUtil(int* a, int* s, int ss, int se, int c){
	if(ss==se){
		s[c]=a[ss];
		//cout << "c: " << c <<  ", s[c]: " << s[c] << endl;
		return(a[ss]);
	}
	int mid=getMid(ss, se);
	s[c]=segTreeUtil(a, s, ss, mid, 2*c+1)+segTreeUtil(a, s, mid+1, se, 2*c+2);
	//cout << "c: " << c <<  ", s[c]: " << s[c] << endl;
	return(s[c]);
}
int* segTree(int* a, int n){
	int h=(int)(ceil(log2(n))); // 2*n-1
	int ts=2*(int)pow(2, h)-1;
	int* s=new int[ts];
	// segment tree with number of nodes=2*n-1
	// each leaf node contains array item and
	// internal nodes contain sum of items from i to j
	// such that i<j<n
	segTreeUtil(a, s, 0, n-1, 0);
	return(s);
}
int getSum(int* s, int ss, int se, int qs, int qe, int si){
	if(qs<=ss and qe>=se){
		return(s[si]);
	}
	if(se<qs or ss>qe){
		return(0);
	}
	int mid=getMid(ss, se);
	return(getSum(s, ss, mid, qs, qe, 2*si+1)+getSum(s, mid+1, se, qs, qe, 2*si+2));
}
void updateUtil(int* s, int ss, int se, int index, int diff, int si){
	if(index<ss or index>se){
		return;
	}
	s[si]+=diff;
	if(ss!=se){
		int mid=getMid(ss, se);
		updateUtil(s, ss, mid, index, diff, 2*si+1);
		updateUtil(s, mid+1, se, index, diff, 2*si+2);
	}

}
void updateArray(int* a, int* s, int ss, int se, int index, int val){
	if(index<ss or index>se){
		cout << "index out of bound." << endl;
		return;
	}
	int diff=val-a[index];
	a[index]=val;
	updateUtil(s, ss, se, index, diff, 0);
}
int main(){
	int a[]={1, 3, 5, 2, 9, 4};
	//{1, 3, 5, 3, 9, 11};
	//
	int n=sizeof(a)/sizeof(a[0]);
	int* s=segTree(a, n);
	//cout << "range sum: " << getSum(s, 0, n-1, 1, 3, 0) << endl;
	updateArray(a, s, 0, n-1, 1, 7);
	for(int i=0;i<2*n-1;i++){
		cout << s[i] << " ";
	}
	return(0);
}