尋ねられるクエリは以下の \(2\) 種類です。

• 貯金箱 \(L,L+1,\dots,R\) に \(X\) 円加算
• 貯金箱 \(P\) に入っている金額を尋ねる

「貯金箱 \(P\) に入っている金額を尋ねる」というクエリに対しては、「最初に貯金箱 \(P\) に入っていた金額」と「クエリによって貯金箱 \(P\) に入った金額」との和を答えればよいので、そうします。

結局、貯金箱 \(L,L+1,\dots,R\) に \(X\) 円加算というクエリを効率的に処理出来ればこの問題に正解できます。
様々な方法がありますが、直接的に加算を扱わなくてよいひとつの方法を示します。

• 貯金箱 \(L,L+1,\dots,R\) への \(X\) 円の加算を、以下の操作に分解します。
  • \(A_L\) に \(X\) 加算
  • \(A_{R+1}\) から \(X\) 減算
• すると、貯金箱 \(k\) に加算された額は \(A_1+A_2+\dots+A_k\) として得られます。
  • 先ほど分解した操作が、貯金箱 \(L,L+1,\dots,R\) に対してのみ \(X\) 加算する操作として働いていることを確認してください。
• 一連の操作は、一点更新・区間和取得ができるデータ構造で実現可能です。例えば、ACL にも実装されている segment tree を使えばよいです。

時間計算量は \(O(N+Q \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/segtree>

using namespace std;
using namespace atcoder;
using ll=long long;

ll op(ll a,ll b){return (a+b);}
ll e(){return 0;}

int main(){
  ll N,Q;
  cin >> N >> Q;
  vector<ll> A(N+5);
  for(ll i=1;i<=N;i++){cin >> A[i];}
  vector<ll> ini(N+5,0);
  segtree<ll,op,e> seg(ini);
  while(Q--){
    ll typ;
    cin >> typ;
    if(typ==1){
      ll L,R,X;
      cin >> L >> R >> X;
      seg.set(L,seg.get(L)+X);
      seg.set(R+1,seg.get(R+1)-X);
    }
    else{
      ll P;
      cin >> P;
      cout << A[P]+seg.prod(0,P+1) << "\n";
    }
  }
  return 0;
}