[BOJ] 구간 합 구하기

구간 합 구하기

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	(2 ≤ N ≤ 10,000, 1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000)	PrefixSum

아니 근데 문제가 세그 트리라는데 제가 세그 트리를 안 써봐가지고 그냥 풀긴 했거든여.. 근데 다들 세그 트리로 풀었다네요

저는 이게 당연히 정해인 줄 알앗는데 ㅠ

그래도 거의 20분 컷 해서 기분은 좋습니다.

포인트는 바뀌는 것을 어떻게 보정해서 더한 값이 같게 만들어질 것인지를 고민하면 풀립니다.

정답 코드

#define MAX 200000001
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
using ll = long long;
using namespace std;

ll preSum[1'000'001];
ll nums[1'000'001];

vector<pair<ll, ll>> changes;
ll fixed_[1'000'001];
ll n, m, k;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> k;
    
    for(int i = 0; i < n; i++){
        cin >> nums[i];
        fixed_[i] = nums[i];
    }
    preSum[0] = nums[0];
    
    for(int i = 1; i < n; i++) preSum[i] += preSum[i-1] + nums[i];
    
    
    
    for(int i = 0; i < m + k; i++){
        ll a, b, c;
        
        cin >> a >> b >> c;
        
        // change
        if(a == 1){
            changes.push_back({b, c - fixed_[b-1]});
            fixed_[b-1] = c;
//            cout << c - numbers[b-1] <<"\n\n";
        }
        // print
        else if(a == 2){
            ll another = 0;
            
            for(pair<ll, ll> p : changes){
                if(!(b <= p.first && p.first <= c)) continue;
                another += p.second;
            }
            
            cout << preSum[c-1] - preSum[b-1] + another + nums[b - 1] << "\n";
        }
        
    }
    return 0;
    
    
    
    

}