提出 72cf7b18-e253-455b-8a30-1d7bab67dba6

コード

#include <bits/stdc++.h>
using namespace std;

int main(){
  long long N,n = 1;
  int Q;
  cin >> N;
  while(n < N) n *= 2;
  vector<long long> seg(n*2,0);
  for(int i = 0;i < N;i++){
    cin >> seg[i+n];
  }
  cin >> Q;
  for(int i = n-1;i > 0;i--) seg[i] = seg[i*2]+seg[i*2+1];
  for(int i = 0;i < Q;i++){
    int query;
    cin >> query;
    if(query == 2){
      int l,r;
      cin >> l >> r;
      l += (n-1),r += (n-1);
      long long ans = 0;
      cerr << "l:" << l << ",r:" << r << ",ans:" << ans << endl;
      while(l != r && l < r){
        if(l % 2 == 1){
          ans += seg[l];
          l++;
        } 
        if(r % 2 == 1){
          r--;
          ans += seg[r];
        }
        l /= 2;
        r /= 2;
        cerr << "l:" << l << ",r:" << r << ",ans:" << ans << endl;
      }
      cout << ans << endl; 
    }
    else{
      int pos,x;
      cin >> pos >> x;
      pos += (n-1);
      seg[pos] = x;
      while(pos != 0){
        pos /= 2;
        seg[pos] = seg[pos*2] + seg[pos*2+1];
      }
    }
  }
}

結果

問題	点数	言語	結果	実行時間	メモリ
SegTree - segment tree	100	C++	AC	82 ms	3864 KiB