백준 11505번 : 구간 곱 구하기 (C++)

문제 : https://www.acmicpc.net/problem/11505

11505번: 구간 곱 구하기

 

 

구간 곱 구하기 문제로 아래 링크의 구간 합 구하기 문제와 매우 유사하다. 마찬가지로 세르먼트트리로 손쉽게 풀 수 있다. 차이점으로는 합 대신 곱 연산을 해야함과 0일때가 있을수 있으므로 update 함수를 조금 다르게 구현해야한다.

구간합구하기: https://www.acmicpc.net/problem/2042

 

 

 

 

 기존 세그먼트트리의 update를 구현할때는 위에서부터 tree의 값을 변경시키면서 내려가지만, 이번에 그렇게 하면 0일때는 하지 못하므로 반대로 leaf 노드부터 업데이트를 해서 root 노드로 올라가야한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>


typedef long long ll;


using namespace std;
vector<ll> l;
vector<ll> seg;


ll seginit(int node, int start, int end){
	
	if(start==end){
		return seg[node] = l[start];
	}

	int mid = (start + end)/2;

	return seg[node] = seginit(node*2, start, mid) + seginit(node*2+1, mid+1, end);
}

void update(int node, int start, int end, int index, ll dif){
	if (!(start <= index && index <= end))
        return;
    
    seg[node] += dif;
 
    if(start != end)
    {
        int mid = (start + end) / 2;
        update(node * 2, start, mid, index, dif);
        update(node * 2 + 1, mid + 1, end, index, dif);
    }

}

ll sum( int node, int start, int end, int left, int right)
{
    if (left > end || right < start)
        return 0;
 
    if (left <= start && end <= right)
        return seg[node];
 
    int mid = (start + end) / 2;
    return sum( node * 2, start, mid, left, right) + sum(node*2+1, mid+1, end, left, right);
}





int main() {	
	
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int n, m, k;

	cin >> n >> m >>k;
	int h = (int)ceil(log2(n));

	l.resize(n+1);
	seg.resize( (1<<(h+1)) + 10 );

	for(int i=1; i<=n; i++)
		cin >> l[i];

	seginit(1, 1, n);

	for(int i=0; i<m+k; i++){
		ll a, b, c;
		cin >> a >> b >> c;
		if(a==1){
			ll d = c - l[b];
			l[b] = c;
			update(1, 1, n, b, d);
		}
		else{
			cout << sum(1, 1, n, b, c) << '\n';
		}
	}

}