(2042) 구간 합 구하기

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

단계별로 풀어보기

44단계(세그먼트 트리 1) 1번째

 

 

 

정말 유명한 자료구조 중 하나인 새그먼트 트리다. 인터넷에 검색하면 많은 설명이 나오므로 생략한다.

예전 계정을 보니 탑다운, 다운탑, 비재귀, 팬윅트리 등 다양한 방식을 연습했던 것 같은데 지금은 기본적인 구현만 하려고 한다.

 

 

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, k;
  
  cin >> n >> m >> k;
  
  int treesize= (1<<(((int)ceil(log2(n)))+1));
  vector<long> v(n+1), segtree(treesize);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  auto init= [&](auto self, int s, int e, int node) -> void {
    if(s==e){
      segtree[node]= v[s];
    }else{
      self(self, s, s+(e-s)/2, node*2);
      self(self, s+(e-s)/2+1, e, node*2+1);
      segtree[node]= segtree[node*2]+segtree[node*2+1];
    }
  };
  
  auto update= [&](auto self, int s, int e, int node, int idx, long val) -> void {
    if(idx<s||e<idx)  return;
    
    if(s==e){
      v[idx]= val;
      segtree[node]= val;
    }else{
      self(self, s, s+(e-s)/2, node*2, idx, val);
      self(self, s+(e-s)/2+1, e, node*2+1, idx, val);
      segtree[node]= segtree[node*2]+segtree[node*2+1];
    }
  };
  
  auto query= [&](auto self, int s, int e, int node, int l, int r) -> long {
    if(r<s||e<l)  return 0;
    
    if(l<=s&&e<=r){
      return segtree[node];
    }else{
      long lsum= self(self, s, s+(e-s)/2, node*2, l, r);
      long rsum= self(self, s+(e-s)/2+1, e, node*2+1, l, r);
      return lsum+rsum;
    }
  };
  
  init(init, 1, n, 1);
  
  for(int i=0;i<m+k;i++){
    long a, b, c;
    
    cin >> a >> b >> c;
    
    if(a==1)  update(update, 1, n, 1, b, c);
    else  cout << query(query, 1, n, 1, b, c) << "\n";
  }
  
  return 0;
}