저번 글에서 완성한 세그먼트 트리 하나로 원래라면 전혀 다른 종류의 세그먼트 트리를 구현해야했던 2가지 문제를 아주 간단히 풀어보겠다.
1. 구간 합 세그먼트 트리
https://www.acmicpc.net/problem/2042
특별히 설명할 것도 없는 가장 기본적인 세그먼트 트리 문제이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//기존에 구현해둔 세그먼트 트리 구조체 부분은 주석 처리
/*
template<typename T> struct segment_tree {
T (*merge)(T, T);
int s,e,N;
vector<T> tree;
segment_tree(vector<T> vec,int start,int end,T (*func)(T, T)) {
s=start;
e=end;
N=e-s+1;
merge=func;
tree.resize(4*N+1);
init(vec,1,start,end);
}
T query(int left,int right,T null) {
return que(left,right,1,s,e,null);
}
void update(int idx,vector<T> val,T (*func)(T, vector<T>)) {
upd(1,s,e,idx,val,func);
}
private:
T init(vector<T> &vec,int node,int start,int end) {
if(start==end) return tree[node]=vec[start];
int mid=(start+end)/2;
return tree[node]=merge(init(vec,node*2,start,mid),init(vec,node*2+1,mid+1,end));
}
T upd(int node,int start,int end,int idx,vector<T> &val,T (*func)(T, vector<T>)) {
if(idx<start||idx>end) return tree[node];
if(start==end) return tree[node]=func(tree[node],val);
int mid=(start+end)/2;
return tree[node]=merge(upd(node*2,start,mid,idx,val,func),upd(node*2+1,mid+1,end,idx,val,func));
}
T que(int left,int right,int node,int start,int end,T null) {
if(right<start||left>end) return null;
if(start>=left&&end<=right) return tree[node];
int mid=(start+end)/2;
return merge(que(left,right,node*2,start,mid,null),que(left,right,node*2+1,mid+1,end,null));
}
};
*/
ll f1(ll a,ll b) {
return a+b;
}
ll f2(ll a,vector<ll> b) {
return b[0];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll N,M,K,t1,t2,t3,Q;
cin>>N>>M>>K;
Q=M+K;
vector<ll> v(N+1);
for(int i=1;i<=N;i++) cin>>v[i];
segment_tree<ll> tree(v,1,N,&f1);
while(Q--) {
cin>>t1>>t2>>t3;
if(t1==1)tree.update(t2,{t3},&f2);
else cout<<tree.query(t2,t3,0)<<"\n";
}
}
기존에 작성한 세그먼트 트리 구조체를 하나도 수정하지 않아 매우 쉽고 빠르게 문제를 풀 수 있었다.
그렇다면 더 복잡한 세그먼트 트리 문제에도 적용이 가능할까?
2. 최대 연속 부분합 세그먼트 트리
https://www.acmicpc.net/problem/16993
노드에 저장 해야될 값도 여러개이고 구간의 값을 합치는 방식이 훨씬 복잡한 최대 연속 부분합 세그먼트 트리 문제이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N,Q,t1,t2,INF=1e12;
//기존에 구현해둔 세그먼트 트리 구조체 부분은 주석 처리
/*
template<typename T> struct segment_tree {
T (*merge)(T, T);
int s,e,N;
vector<T> tree;
segment_tree(vector<T> vec,int start,int end,T (*func)(T, T)) {
s=start;
e=end;
N=e-s+1;
merge=func;
tree.resize(4*N+1);
init(vec,1,start,end);
}
T query(int left,int right,T null) {
return que(left,right,1,s,e,null);
}
void update(int idx,vector<T> val,T (*func)(T, vector<T>)) {
upd(1,s,e,idx,val,func);
}
private:
T init(vector<T> &vec,int node,int start,int end) {
if(start==end) return tree[node]=vec[start];
int mid=(start+end)/2;
return tree[node]=merge(init(vec,node*2,start,mid),init(vec,node*2+1,mid+1,end));
}
T upd(int node,int start,int end,int idx,vector<T> &val,T (*func)(T, vector<T>)) {
if(idx<start||idx>end) return tree[node];
if(start==end) return tree[node]=func(tree[node],val);
int mid=(start+end)/2;
return tree[node]=merge(upd(node*2,start,mid,idx,val,func),upd(node*2+1,mid+1,end,idx,val,func));
}
T que(int left,int right,int node,int start,int end,T null) {
if(right<start||left>end) return null;
if(start>=left&&end<=right) return tree[node];
int mid=(start+end)/2;
return merge(que(left,right,node*2,start,mid,null),que(left,right,node*2+1,mid+1,end,null));
}
};
*/
struct node { //노드로 사용할 구조체
ll lval,rval,val,all;
};
node merge(node l,node r) { //두 구간의 값을 합치는 함수
return {max(l.lval,l.all+r.lval),max(r.rval,r.all+l.rval),max(max(l.val,r.val),l.rval+r.lval),l.all+r.all};
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N;
vector<node> v(N+1);
for(int i=1;i<=N;i++) {
cin>>t1;
v[i]={t1,t1,t1,t1};
}
segment_tree<node> tree(v,1,N,&merge);
cin>>Q;
while(Q--)
{
cin>>t1>>t2;
cout<<tree.query(t1,t2,{-INF,-INF,-INF,-INF}).val<<"\n";
}
}
마찬가지로 매우 쉽고 빠르게 문제를 푸는 것이 가능했다.
댓글남기기