BasicSegmentTree.cpp

/**
*
*			Arif Hosan
*American International University Bangladesh
*
**/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<cstring>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<sstream>
#include<functional>
#include<stack>
#include<set>
#define PI 2*acos(0.0)
#define SIZE 1000000
#define endl '\n'
int caseno = 1;
#define CP() printf("Case %d: ",caseno++)
#define R() freopen("in.txt","r",stdin)
#define W() freopen("out.txt","w",stdout)
#define RW R(); W()
#define SFI(_i) scanf("%d",&_i)
#define SFII(_i,_ii) scanf("%d%d",&_i,&_ii)
#define SFD(_i) scanf("%lf",&_i)
#define SFC(_c) scanf("%c",&_c)
#define PFIL(_i) printf("%d\n",_i)
#define PFI(_i) printf("%d",_i)
#define PFSL(_i) printf("%s\n",_i)
#define PFS(_i) printf("%s",_i)
#define NL printf("\n")
#define SPC printf(" ")
#define ALL(_c) _c.begin(),_c.end()
#define ITE(_a,_b) map<_a,_b>::iterator
#define MEM(_c,_v) memset(_c,_v,sizeof(_c))
#define FOR(i,a,b) for(i=(a);i<(b);i++)
#define REV(i,a,b) for(i=(a);i>=(b);i--)
#define valid(nx,ny) nx>=0 && nx<30 && ny>=0 && ny<30
using namespace std;

//Segment tree needs more than 2*n size.
#define MX 100
int arr[MX], tree[MX * 3];

int treeSize(int N) {
	int sz = 1;
	while (sz < N) sz <<= 1;
	return sz << 1;
}

void init(int node,int b,int e) {
	//Range values are One, so leaf node. Assigning value to the node.
	if (b == e) {
		tree[node] = arr[b];
		return;
	}

	//Finding left and right node index
	int left = 2 * node;
	int right = left + 1;

	//Finding range of next init call
	int mid=(b + e) / 2;
	
	init(left, b, mid);
	init(right, mid + 1, e);

	//Assigning left and right childs value to the parent node.
	tree[node] = tree[left] + tree[right];
}

int query(int node, int b, int e, int i, int j) {
	//If query range is out of tree segment, returning 0
	if (j<b || i>e) return 0;

	//If Tree range is inside query range , return value of current node
	if (b >= i && j >= e) return tree[node];

	int left = node * 2;
	int right=left + 1;
	int mid = (b + e) / 2;

	//Total sum is the sum of all subqueries
	return query(left, b, mid, i, j) + query(right, mid + 1, e, i, j);
}

void update(int node, int b, int e, int i, int val) {
	if (i<b || i>e) return;
	if (b==e) { 
		tree[node] = val; 
		return;
	}

	int left = node * 2;
	int right = left + 1;
	int mid = (b + e) / 2;
	
	update(left, b, mid, i, val);
	update(right, mid + 1, e, i, val);
	
	tree[node] = tree[left] + tree[right];
}

int main() {
	int i, j;
	int arr2[] = { 0, 4, -9, 3, 7, 1, 0, 2 };
	FOR(i, 0, 8) arr[i] = arr2[i];
	
	//cout << treeSize(7) << endl;

	//Calling based on 1 index, 0 index based calling won't work due to (index*2) operation
	init(1, 1, 7);
	
	/*FOR(i, 1, 15) {
		cout << "Node: " << i << " Value: " << tree[i] << endl;
	}

	cout << "Query of(1-5): " << query(1, 1, 7, 1, 5) << endl;
	cout << "Updating index 5 with -5! \n\n"; update(1, 1, 7, 5, -5);

	FOR(i, 1, 15) {
		cout << "Node: " << i << " Value: " << tree[i] << endl;
	}
	cout << "Query of(1-5): " << query(1, 1, 7, 1, 5) << endl;*/
	return 0;
}