커피숍2

관련문제 

2020/02/14 - [BOJ/C++] - 구간 합 구하기

불러오는 중입니다...

 

#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
void update(vector<ll> &tree, int node, ll diff, int idx, int start, int end) {
    if (idx < start || end < idx) return;
    tree[node] += diff;
 
    if (start != end) {
        update(tree, node*2, diff, idx, start, (start+end)/2);
        update(tree, node*2+1, diff, idx, (start+end)/2+1, end);
        
    }
}
ll sum(vector<ll> &tree, int node, int left, int right, int start, int end) {
    //[start, end]밖에 있는 경우 
    //[left, right]가 [start, end]를 포함할때 
    //그 외 
 
    if (right < start || end < left) return 0;
    else if (left <= start && end <= right) return tree[node];
    else {
        return sum(tree, node*2, left, right, start, (start+end)/2) + sum(tree, node*2+1, left, right, (start+end)/2+1, end);
    }
}
ll init(vector<ll> &tree, vector<ll> &nums, int node, int start, int end) {
    if (start == end) return tree[node] = nums[start];
    return tree[node] = init(tree, nums, node*2, start, (start+end)/2) + init(tree, nums, node*2+1, (start+end)/2+1, end);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q;
    cin >> n >> q;
 
    int h = (int)ceil(log2(n));
    int tree_h = 1<<(h+1);
 
    vector<ll> nums, tree(tree_h);
 
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        nums.push_back(tmp);
    }
 
    init(tree, nums, 1, 0, n-1);
 
    while(q--) {
        int x, y, a, b;
        
        cin >> x >> y >> a >> b;
 
        x--;y--;a--;
        if (x > y) {
            int tmp = x;
            x = y;
            y = tmp;
        }
        cout << sum(tree, 1, x, y, 0, n-1) << '\n';
 
        ll diff = b - nums[a];
        nums[a] = b;
        update(tree, 1, diff, a, 0, n-1);
 
    }
    return 0;
}