(14287) 회사 문화 3

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

단계별로 풀어보기

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

 

 

 

이전 문제와 다르게 조상 노드가 범위인 갱신 쿼리가 들어온다. 반대로 생각하면 어떤 노드의 서브트리에 존재하는 노드에 적용되는 갱신은 이 노드도 온전히 영향을 받는다. 따라서 1번 쿼리를 받으면 단일 노드만 갱신하고, 2번 쿼리를 받았을 때 해당 노드를 루트로 하는 서브트리의 합을 출력하면 된다.

 

 

 

(정답 사진 업로드 깜빡함)

#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, cnt;
  
  cin >> n >> m >> cnt; // cnt는 사장 상사 입력 -1 처리용
  
  vector<int> in(n+1), out(n+1);
  vector<vector<int>> adj(n+1);
  
  for(int i=2;i<=n;i++){
    int x;
    
    cin >> x;
    
    adj[x].push_back(i);
  }
  
  auto dfs= [&](auto self, int now, int prev) -> void {
    in[now]= ++cnt;
    
    for(int next:adj[now]){
      if(next==prev)  continue;
      
      self(self, next, now);
    }
    
    out[now]= cnt;
  };
  
  cnt= 0;
  dfs(dfs, 1, 0);
  
  int treesize= (1<<(((int)ceil(log2(n)))+1));
  vector<long> v(n+1), segtree(treesize);
  
  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, w;
      
      cin >> i >> w;
      
      update(update, 1, n, 1, in[i], w);
    }else{
      int i;
      
      cin >> i;
      
      cout << query(query, 1, n, 1, in[i], out[i]) << "\n";
    }
  }
  
  return 0;
}