Balanced Brackets using Segment Tree - BRCKTS in C++

test1.cpp

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

class Node {
	public:
		int needLeft;
		int needRight;
		Node(){
			needLeft = 0;
			needRight = 0;
		}
	};

void construct(string arr,Node tree[], int index, int start, int end){
	int mid,newMatches;
	if(start == end){
		if(arr[start] == '('){
			tree[index].needRight = 1;
		}
		else{
			tree[index].needLeft = 1;
		}
	}
	else{
		mid = (start+end)/2;
		construct(arr,tree,2*index,start,mid);
		construct(arr,tree,(2*index)+1,mid+1,end);
		newMatches = min(tree[2*index].needRight,tree[(2*index)+1].needLeft);
		tree[index].needLeft = tree[2*index].needLeft + tree[(2*index)+1].needLeft - newMatches;
		tree[index].needRight = tree[2*index].needRight + tree[(2*index)+1].needRight - newMatches;
	}
}

void modify(Node tree[], int index, int startIndex, int start, int end){
	int mid,newMatches;
	if(start == end){
		if(tree[startIndex].needLeft == 1){
			tree[startIndex].needLeft = 0;
			tree[startIndex].needRight = 1;
		}
		else{
			tree[startIndex].needLeft = 1;
			tree[startIndex].needRight = 0;
		}
		return;
	}	
	else{
		mid = (start+end)/2;
		if(index <= mid){
			modify(tree, index, 2*startIndex, start, mid);
		}
		else{
			modify(tree, index, (2*startIndex)+1, mid+1, end);
		}
		newMatches = min(tree[2*startIndex].needRight,tree[(2*startIndex)+1].needLeft);
		tree[startIndex].needLeft = tree[2*startIndex].needLeft + tree[(2*startIndex)+1].needLeft - newMatches;
		tree[startIndex].needRight = tree[2*startIndex].needRight + tree[(2*startIndex)+1].needRight - newMatches;
	}
}

int main() {
	//For Fast IO
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n,height,i,testcase,m,k,operation;
	string arr;
	for(testcase=1; testcase<=10; testcase++){
		cin >> n;
		cin >> arr;
		height = int(ceil(log(n)/log(2)));
		Node tree[int(pow(2,height+1))];
		construct(arr,tree,1,0,n-1);
		cout<<"Test "<<testcase<<":"<<endl;
		cin >> m;
		for(operation=1; operation<=m; operation++){
			cin >> k;
			if(k == 0){
				if(tree[1].needLeft == 0 && tree[1].needRight == 0){
					cout<<"YES"<<endl;
				}
				else{
					cout<<"NO"<<endl;
				}
			}
			else{
				modify(tree,k-1,1,0,n-1);
			}
		}
	}
	return 0;
}