SegTreeSimulator.cpp

#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define lli long long int
#define rep(i,n,z) for(int i=z;i<n;i++)
#define rrep(i,z) for(int i=z;i>=0;i--)
#define nl cout<<endl
#define vi vector<int>
#define vlli vector<long long int>
#define umap unordered_map
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define ipair pair <int,int>
#define llipair pair <lli,lli>
#define pq priority_queue
#define displaymatrix(a,m,n) for(int i=0;i<m;i++){for(int j=0;j<n;j++)cout<<a[i][j]<<" ";cout<<endl;}
#define printarray(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}nl;
#define vinput(a,n) vlli a(n);rep(i,n,0)cin>>a[i]
#define ainput(a,n) rep(i,n,0)cin>>a[i]
#define SO(a) sort(a.begin(),a.end())
#define all(x) (x).begin(),(x).end()
#define SOP(a,comp) sort(a.begin(),a.end(),comp)
#define inf INT_MAX
// #define endl '\n'

//template credits: https://github.com/Ashishgup1/Competitive-Coding/blob/master/Segment%20Tree.cpp

lli S=1e5+5;
int n;
vector <int> a;

struct data
{
	//Use required attributes
	int mn;

	//Default Values
	data(){
		mn = 1e9;
	}
};

struct SegTree
{
	int N;
	vector<data> st;
	vector<bool> cLazy;
	vector<int> lazy;

	void init(int n)
	{
		N = n;
		st.resize(4 * N + 5);
		cLazy.assign(4 * N + 5, false);
		lazy.assign(4 * N + 5, 0);
	}

	//Write reqd merge functions
	void merge(data &cur, data &l, data &r) 
	{
		cur.mn = min(l.mn, r.mn);
	}
	
	//Handle lazy propagation appriopriately
	void propagate(int node, int L, int R)
	{
		if(L != R)
		{
			cLazy[node*2] = 1;
			cLazy[node*2 + 1] = 1;
			lazy[node*2] = lazy[node];
			lazy[node*2 + 1] = lazy[node]; 
		}
		else{
			a[L-1]=lazy[node];
		}
		st[node].mn = lazy[node];
		cLazy[node] = 0;
	}

	void build(int node, int L, int R)
	{
		if(L==R)
		{
			st[node].mn = a[L];
			return;
		}
		int M=(L + R)/2;
		build(node*2, L, M);
		build(node*2 + 1, M + 1, R);
		merge(st[node], st[node*2], st[node*2+1]);
	}

	data Query(int node, int L, int R, int i, int j)
	{
		if(cLazy[node])
			propagate(node, L, R);
		if(j<L || i>R)
			return data();
		if(i<=L && R<=j)
			return st[node];
		int M = (L + R)/2;
		data left=Query(node*2, L, M, i, j);
		data right=Query(node*2 + 1, M + 1, R, i, j);
		data cur;
		merge(cur, left, right);
		return cur;
	}

	data pQuery(int node, int L, int R, int pos)
	{
		if(cLazy[node])
			propagate(node, L, R);
		if(L == R)
		{
			return st[node];
		}
		int M = (L + R)/2;
		if(pos <= M)
			return pQuery(node*2, L, M, pos);
		else
			return pQuery(node*2 + 1, M + 1, R, pos);
	}	

	void Update(int node, int L, int R, int i, int j, int val)
	{
		if(cLazy[node])
			propagate(node, L, R);
		if(j<L || i>R)
			return;
		if(i<=L && R<=j)
		{
			cLazy[node] = 1;
			lazy[node] = val;
			propagate(node, L, R);
			return;
		}
		int M = (L + R)/2;
		Update(node*2, L, M, i, j, val);
		Update(node*2 + 1, M + 1, R, i, j, val);
		merge(st[node], st[node*2], st[node*2 + 1]);
	}

	void pUpdate(int node, int L, int R, int pos, int val)
	{
		if(cLazy[node])
			propagate(node, L, R);
		if(L == R)
		{
			cLazy[node] = 1;
			lazy[node] = val;
			propagate(node, L, R);
			a[L-1]=val;
			return;
		}
		int M = (L + R)/2;
		if(pos <= M)
			pUpdate(node*2, L, M, pos, val);
		else
			pUpdate(node*2 + 1, M + 1, R, pos, val);
		merge(st[node], st[node*2], st[node*2 + 1]);
	}

	data query(int pos)
	{
		return pQuery(1, 1, N, pos);
	}

	data query(int l, int r)
	{
		return Query(1, 1, N, l, r);
	}

	void update(int pos, int val)
	{
		pUpdate(1, 1, N, pos, val);
	}

	void update(int l, int r, int val)
	{
		Update(1, 1, N, l, r, val);
	}
};

int main()
{
	fastio;
	SegTree tree; // Defining the structure
	int o,n,x,l,r,val;

		while(1){
			cin>>o;

			switch(o){
			case 1:
				cin>>n;
				S=4*n;
				tree.init(n);
				a.resize(n+1);
				rep(i,n,0)cin>>a[i];
				tree.build(1,0,n-1);

				cout<<"Tree build successful. press 6 to view."<<endl;
				break;
			case 2:
				cout<<"entering case with top value:"<<tree.st[1].mn<<" enter option:";
				cin>>x;
				cout<<tree.query(x).mn<<endl; 
				break;
			case 3:
				cin>>l>>r;
				cout<<tree.query(l,r).mn<<endl;
				break;
			case 4:
				cin>>x>>val;
				tree.update(x,val);
				cout<<"Update processed. press 6 to view."<<endl;
				break;
			case 5:
				cin>>l>>r>>val;
				tree.update(l,r,val);
				cout<<"Update proecessed. press 6 to view."<<endl;
				break;
			case 6:
				cout<<"a :";
				rep(i,n,0)cout<<a[i]<<" ";
				nl;

				cout<<"st :";
				rep(i,S,0)cout<<tree.st[i].mn<<" ";
				nl;

				cout<<"cLazy :";
				rep(i,S,0)cout<<tree.cLazy[i]<<" ";
				nl;
				
				cout<<"lazy :";
				rep(i,S,0)cout<<tree.lazy[i]<<" ";
				nl;

				break;
		}
	}
}

/*

	RULES:
	1 n [... n integers ...] : Initialize the SegTree
	2 x : queries location x
	3 l r: Queries the range l to r
	4 x val: updates the position x to val
	5 l r val: updates the range l to r as val
	6 : Displays all the arrays at once.
*/

To use the simulator, follow the input pattern:

    1 n [... n integers ...] : Initialize the SegTree
2 x : queries location x
3 l r: Queries the range l to r
4 x val: updates the position x to val
5 l r val: updates the range l to r as val
6 : Displays all the arrays at once.