(10999) 구간 합 구하기 2

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

단계별로 풀어보기

52단계(세그먼트 트리 2) 4번째

 

 

 

그 동안 구간 갱신은 누적합 배열을 이용해 단일 노드 갱신으로 바꿀 수 있었지만 이 문제에서는 불가능하고 느리게 갱신되는 세그먼트 트리를 구현해야 한다. 어떤 단일 노드를 갱신하는 과정은 O(log N)이 걸리고, 구간의 모든 단일 노드를 갱신하려면 O(N log N)이 걸린다. 하지만 갱신된 단일 노드의 값이 즉시 필요한 것이 아니기 때문에 이를 lazy 배열에 저장해둔 뒤 필요할 때 갱신을 해주는 것이 느린 갱신의 아이디어다.

 

 

 

#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), lazy(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 updatelazy= [&](int s, int e, int node) -> void {
    if(lazy[node]){
      segtree[node]+= (e-s+1)*lazy[node];
      
      if(s!=e){
        lazy[node*2]+= lazy[node];
        lazy[node*2+1]+= lazy[node];
      }
      
      lazy[node]= 0;
    }
  };
  
  auto update= [&](auto self, int s, int e, int node, int l, int r, long val) -> void {
    updatelazy(s, e, node);
    
    if(r<s||e<l)  return;
    
    if(l<=s&&e<=r){
      segtree[node]+= (e-s+1)*val;
      
      if(s!=e){
        lazy[node*2]+= val;
        lazy[node*2+1]+= val;
      }
    }else{
      self(self, s, s+(e-s)/2, node*2, l, r, val);
      self(self, s+(e-s)/2+1, e, node*2+1, l, r, 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 {
    updatelazy(s, e, node);
    
    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++){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    if(a==1){
      long d;
      
      cin >> d;
      
      update(update, 1, n, 1, b, c, d);
    }else{
      cout << query(query, 1, n, 1, b, c) << "\n";
    }
  }
  
  return 0;
}