提出 657667dd-c076-48a6-bb4c-1a47715a3082

コード

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

int main(){
  long long N,n = 1;
  int Q;
  cin >> N >> Q;
  while(n < N) n *= 2;
  vector<long long> seg(n*2,0);
  for(int i = 0;i < N;i++)cin >> seg[i+n];
  for(int i = n-1;i > 0;i--) seg[i] = seg[i*2]+seg[i*2+1];
  for(int i = 1;i < n*2;i++){
  }
  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;
      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;
      }
      cout << ans << endl; 
    }
    else{
      int pos,x;
      cin >> pos >> x;
      pos += (n-1);
      seg[pos] = x;
      while(pos != 0){
        if(pos % 2 == 1)pos--;
        pos /= 2;
        seg[pos] += x;
      }
    }
  }
}

結果

問題	点数	言語	結果	実行時間	メモリ
SegTree. segment tree	0	C++ (gcc)	RE	84 ms	3860 KiB