(16975) 수열과 쿼리 21

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

단계별로 풀어보기

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

 

 

 

업데이트가 단일 값이 아닌 구간의 변경으로 이루어지지만 응답 쿼리는 단일 값으로만 주어지기 때문에 나중에 배우는 느리게 갱신되는 새그먼트 트리를 쓸 필요가 없다. 대신 누적합 배열을 이용하면 된다.

새그먼트 트리로 주어진 배열 A가 아닌 값의 변화량의 누적합 배열 B를 관리한다.

i~j번 배열에 k를 더하는 연산은, 배열 B의 i번째 값에 k를 더하고 j+1번째 값에 -k를 더하면 된다.

A(x)의 값을 물어본다면 배열의 최초값 A0(x)에 배열 B의 1~x번째 구간합을 더하면 된다.

 

 

 

#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;
  
  cin >> n;
  
  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];
  
  cin >> m;
  
  auto update= [&](auto self, int s, int e, int node, int idx, long val) -> void {
    if(idx<s||e<idx)  return;
    
    if(s==e){
      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;
    }
  };
  
  while(m--){
    int q;
    
    cin >> q;
    
    if(q==1){
      int i, j, k;
      
      cin >> i >> j >> k;
      
      update(update, 1, n, 1, i, k);
      if(j<n)  update(update, 1, n, 1, j+1, -k);
    }else{
      int x;
      
      cin >> x;
      
      cout << v[x]+query(query, 1, n, 1, 1, x) << "\n";
    }
  }
  
  return 0;
}