백준1275 커피숍2 작성일 2019-04-07 | In PS 문제 링크 http://icpc.me/1275 사용 알고리즘 Segment Tree 시간복잡도 O(Q log N) 풀이 너무 대놓고 세그먼트 트리를 쓰라고 문제에서 말해주고 있습니다. update와 query만 이쁘게 구현해주면 됩니다. 전체 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Seg{ ll tree[401010]; int bias; void init(int n){ for(bias=1; bias<n; bias<<=1); } void build(){ for(int i=bias-1; i>=1; i--){ tree[i] = tree[i<<1] + tree[i<<1|1]; } } void update(int x, ll v){ x |= bias; tree[x] = v; while(x >>= 1){ tree[x] = tree[x<<1] + tree[x<<1|1]; } } ll query(int l, int r){ l |= bias, r |= bias; ll ret = 0; while(l < r){ if(l & 1) ret += tree[l++]; if(!(r & 1)) ret += tree[r--]; l >>= 1, r >>= 1; } if(l == r) ret += tree[l]; return ret; } } seg; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; seg.init(n); for(int i=1; i<=n; i++){ cin >> seg.tree[i | seg.bias]; } seg.build(); while(q--){ int x, y, a; ll b; cin >> x >> y >> a >> b; if(x > y) swap(x, y); cout << seg.query(x, y) << "\n"; seg.update(a, b); } return 0; }