백준 알고리즘 2042번 : 구간 합 구하기

링크

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

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 << 21];
	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,m,k; cin >> n >> m >> k;
  for(int i = 1; i <= n; i++){
    int t; cin >> t;
    ST.update(i, t);
  }
  while(m + k--){
    int a,b,c; cin >> a >> b >> c;
    if(a == 1) ST.update(b, c);
    else cout << ST.query(b, c) << "\n";
  }
}

구간 합 세그먼트 트리를 이용해주면 됩니다