[백준] 2268번 수들의 합 7 C++ 코드

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

int n,m,s,x,y;
vector<ll> tree;
vector<ll> a;

void init(int node, int start, int end) {
  if (start == end) {
    tree[node] = a[start];
    return;
  } else {
    int mid = (start + end) / 2;
    init(node*2, start, mid);
    init(node*2 + 1, mid + 1, end);
    tree[node] = tree[node*2] + tree[node*2 + 1];
  }
}

ll query(int node, int start, int end, int left, int right) {
  if(left > end || start > right) return 0;
  if(left <= start && right >= end) return tree[node];
  int mid = (start + end) / 2;
  ll lsum = query(node*2, start, mid, left, right);
  ll rsum = query(node*2 + 1, mid + 1, end, left, right);
  return lsum + rsum;
}

void update(int node, int start, int end, int idx, ll val) {
  if(idx > end || idx < start) return;
  if(start == end) {
    a[idx] = val;
    tree[node] = a[start];
    return;
  } else {
    int mid = (start + end) / 2;
    update(node*2, start, mid, idx, val);
    update(node*2 + 1, mid + 1, end, idx, val);
    tree[node] = tree[node*2] + tree[node*2 + 1];
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  int h = (int)ceil(log2(n));
  int tree_size = (1 << (h + 1));
  a.resize(n);
  tree.resize(tree_size);
  for(int i = 0; i < n; i++) a[i] = 0;
  
  init(1, 0, n -1);

  for(int i = 0; i < m; i++) {
    cin >> s >> x >> y;
    if(s == 0) {
      // y가 x보다 큰 보장이 없다
      if(x > y) {
        int tmp = x;
        x = y;
        y = tmp;
      }
      cout << query(1, 0, n - 1, x-1, y-1) << '\n';
    } else if(s == 1) {
      update(1,0,n-1, x-1,y);
    }
  }
  return 0;
}

풀이

구간합을 만들어서 푸는 문제지만, 변경이 자주 일어나기 때문에 구간합을 사용하는 것은 비효율적이다. 따라서 세그먼트 트리를 이용해서 수들의 합을 찾아주었다. 변경이 일어나도 빠르게 수정이 가능하고 값을 얻어낼 수 있기 때문이다.

 

틀린 이유

문제를 읽을 때, i > j 인 것을 봤지만 코드를 작성하면서 잊은 게 문제였다. 이런 조건은 종이에 써두거나 주석을 달거나 해야겠다. 그리고 코드 작성이 끝나면 문제를 다시 한 번 읽어보고 조건에 부합한지 확인하는 것에 더 신경을 써야겠다.