커피숍2

#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef long long int ll;
 
void update(vector<ll> &tree, int node, ll diff, int idx, int start, int end)
{
    //범위 안에 포함되어있을 때
    //아닐 때
    if (start > idx || idx > end)
    {
        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)
{
    //[left, right]가 [start, end]를 포함할 때
    //[left, right]가 [start, end]에 포함될 때
    //밖에 있을 때
 
    if (right < start || end < left)
    {
        //(3)
        return 0;
    }
    else if (left <= start && end <= right)
    {
        //(1)
        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 initTree(vector<ll> &tree, vector<ll> &nums, int node, int start, int end)
{
    if (start == end)
        return tree[node] = nums[start];
    return tree[node] = initTree(tree, nums, node * 2, start, (start + end) / 2) + initTree(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;
 
    //n개의 정수
    vector<ll> nums;
    for (int i = 0; i < n; i++)
    {
        int n;
        cin >> n;
        nums.push_back(n);
    }
 
    int height = (int)ceil(log2(n));
    int tree_size = 1 << (height + 1);
 
    vector<ll> tree(tree_size);
 
    initTree(tree, nums, 1, 0, n - 1);
 
    for (int i = 0; i < q; i++)
    {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
 
        if (x > y)
        {
            int tmp = x;
            x = y;
            y = tmp;
        }
        x--;
        y--;
        cout << sum(tree, 1, x, y, 0, n - 1) << '\n';
        a--;
        ll diff = b - nums[a];
        nums[a] = b;
        update(tree, 1, diff, a, 0, n - 1);
    }
 
    return 0;
}