範囲の合計 [yukicoder No.789] - はまやんはまやんはまやん

前提知識

動的構築セグメントツリー

解説

このクエリは動的構築セグメントツリーで解決できるので持ってる人は貼るのが最速。
持っていない場合は、今回はクエリ先読みできるので、座圧してBITで処理するのが早い。
　
自分は動的構築セグメントツリー持ってたので貼った。
理論はセグメントツリーがわかっていればそんなに難しくないが、どちらかというと先にtrieを学習したほうがいい。
trieも動的に木を構築していくが、動的構築セグメントツリーもそのやり方と全く同じで木を構築する。
trieの方が覚えておくべきだと思うので、そちらを先に学習するといい。
そちらがわかっていれば、動的構築セグメントツリーでどのように動的構築していくかをつかみやすいだろう。

int N;
DynamicSegTree dst;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    ll ans = 0;
    rep(i, 0, N) {
        int t, x, y; cin >> t >> x >> y;
        if (t == 0) {
            dst.add(x, y);
        }
        else {
            ans += dst.get(x, y+1);
        }
    }

    cout << ans << endl;
}