백준 알고리즘 1275번 : 커피숍2

링크

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

sol1) 구간 합 세그먼트 트리

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

struct SegTree {
	int tree[1 << 22];
	int sz = 1 << 20;
	void construct() {
		for (int i = sz - 1; i > 0; i--) {
			tree[i] = tree[i << 1] + tree[i << 1 | 1];
		}
	}
  // 1 - indexed
	void update(int i, int val) {
		--i |= sz; tree[i] = val;
		while (i >>= 1) {
			tree[i] = tree[i << 1] + tree[i << 1 | 1];
		}
	}
  // [l, r]
	int query(int l, int r) {
		--l |= sz, --r |= sz;
		int ret = 0;
		while (l <= r) {
			if (l & 1) ret += tree[l++];
			if (~r & 1) ret += tree[r--];
			l >>= 1, r >>= 1;
		}
		return ret;
	}
}ST;

int32_t main() {
  fastio;
  int n,q; cin >> n >> q;
  for(int i = 1; i <= n; i++){
    int t; cin >> t;
    ST.update(i, t);
  }
  while(q--){
    int a,b,x,y; cin >> x >> y >> a >> b;
    if(x > y) swap(x, y);
    cout << ST.query(x, y) << "\n";
    ST.update(a, b);
  }
}

구간 합 세그먼트 트리를 이용해야하는 문제였습니다.
주의해야할 건 x가 y보다 클 때 바꿔줘야한다는 것입니다