Shared code

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

struct node{
	long ml=100000000000L;
	long mr=10000000000L;
	long sz=0;
};

node merge(node a, node b){
	node t;
	t.ml=min(a.ml, b.ml+a.sz);
	t.mr=min(a.mr+b.sz, b.mr);
	t.sz=a.sz+b.sz;
	return t;
}

class segTree{
	vector<node> tr;
	int N=1;
	public:
	segTree(int n){
		while(N<n)
			N*=2;
		
		for(int i=0; i<N*2; i++)
		{
			node t;
			t.sz=1;
			tr.push_back(t);
		}
	}
	void update(int a, int v){
		a+=N;
		tr[a].ml=v;
		tr[a].mr=v;
		while(a>1)
		{
			a/=2;
			tr[a]=merge(tr[a*2], tr[a*2+1]);
		}
	}
	long squery(int ind){
		return min(query(0, ind).mr, query(ind, N-1).ml);
	}

	node query(int l, int r){
		node t;
		node tp;
		l+=N; r+=N;
		//cout<<l<<' '<<r<<"?"<<endl;
		while(l<r){
			if(l%2==1)	
				t=merge(t,tr[l++]);
			if(r%2==0)
				tp=merge(tr[r--], tp);
			l/=2; r/=2;
			//cout<<t.va<<' '<<tp.va<<endl;
			//cout<<l<<' '<<r<<endl;
		}
		if(l==r){
			t=merge(t, tr[l]);
		}
		
		return merge(t,tp);
	}
};

int main() {
	cin.tie(NULL);
	int N,Q; cin>>N>>Q;
	segTree tr(N);
	for(int i=0; i<N; i++)
	{
		int t; cin>>t;
		tr.update(i, t);
	}

	while(Q--){
		int t,a,b; cin>>t;
		if(t==2){
			cin>>a;
			cout<<tr.squery(a-1)<<"\n";
		}
		else{
			cin>>a>>b;
			tr.update(a-1,b);
		}
	}
	cout<<flush;
}