백준 17400 깃발춤

https://www.acmicpc.net/problem/17400

숭고한 공식 풀이는 여기서 보실 수 있습니다.

segment tree 문제입니다. segment tree에 관련된 내용은 여기서 보실 수 있습니다.

하나의 세그먼트 트리를 이용하여도 풀리지만, 직관적으로 짝수번째 index를 갖는 공연자의 카리스마의 합을 저장하는 세그먼트 트리, 홀수번째 index를 갖는 공연자의 카리스마의 합을 저장하는 세그먼트 트리 2개를 만들었습니다.

인덱스 x를 (x+1)//2 에 저장하였습니다. (즉, 1은 홀수에서 1, 2는 짝수에서 1, 3은 홀수에서 2 …)

따라서 구간 [l,r]=odd[l//2+1,(r+1)//2] + even[l//2+1,(r+1)//2] 로 나타낼 수 있습니다.

(l,r이 (짝수,짝수),(짝수,홀수),(홀수,짝수),(홀수,홀수) 4가지 경우를 나누어 구간을 구해도 무방합니다. )

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int SZ=300005;
ll seg_odd[4*SZ];
ll seg_even[4*SZ];
int n,q;
void seg_update(ll *seg, int idx, int l, int r, int f, ll d){
	if(f<l || r<f) return;
	seg[idx]+=d;
	if(l==r) return;
	seg_update(seg,idx*2,l,(l+r)/2,f,d);
	seg_update(seg,idx*2+1,(l+r)/2+1,r,f,d);
}
ll seg_find(ll *seg, int idx, int l, int r, int fl, int fr){
	if(r<fl || fr<l) return 0;
	if(fl<=l && r<=fr) return seg[idx];
	return seg_find(seg,2*idx,l,(l+r)/2,fl,fr)+seg_find(seg,2*idx+1,(l+r)/2+1,r,fl,fr);
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		ll x; cin>>x;
		if(i%2==1) seg_update(seg_odd,1,1,(n+1)/2,(i+1)/2,x);
		else seg_update(seg_even,1,1,(n+1)/2,i/2,x);
	}
	while(q--){
		int xx; cin>>xx;
		if(xx==1){
			int l,r; cin>>l>>r;
			cout<<llabs(seg_find(seg_odd,1,1,(n+1)/2,l/2+1,(r+1)/2)-seg_find(seg_even,1,1,(n+1)/2,(l+1)/2,r/2))<<'\n';
		}
		else{
			int f,d; cin>>f>>d;
			if(f%2==1) seg_update(seg_odd,1,1,(n+1)/2,(f+1)/2,d);
			else seg_update(seg_even,1,1,(n+1)/2,f/2,d);
		}
	}
	return 0;
}