セグメント木で segtree[i] += x がしたい

2020/12/21 更新
以下のリプライを頂きましたので, queue ではなく, 最後に参照された index のみ保持する実装に変更しました.

やりたいこと

1点更新区間和取得のセグメント木で 1 点更新を行う際, 多くは segtree.set_val(index, value) のように関数として呼んでいると思います.
これが嫌なので, 1 点更新をsegtree[i] = xやsegtree[i] += seg.fold(l, r)みたいにやることを目指します.

前提知識

セグメント木についてはここでは説明しません. 調べるとたくさん記事が出てくるので, そっちを見てください.
実装は C++ です.

アイディア

operator[]を呼ばれるたびにアクセスされた場所を updateできればいいのですが, ちょっと厳しいです.(もしかしたらできるかもしれません. できたら嬉しい.)

よく考えると, foldをする前にoperator[]でアクセスされた部分のみ更新できれば大丈夫そうなので, operator[]を呼んだ時にその場所を記録だけして, fold が呼ばれたときに全部解消します.

前回 operator[] で参照された index を保持する変数を 1 つ用意しておいて, operator[] または fold が呼び出されるたびに, その場所を更新します.

operator[] が呼ばれたとき

内部でqueueやstackなどを持って, operator[]が呼ばれるたびに, そのindexを記録します.
はじめに前回の operator[] でアクセスされた index について更新を行います.
その後, 今アクセスする index を新たに記録します.

foldするとき

foldする前に記録した部分を更新します.

実装例

非再帰実装です.
last_referenced に最後にアクセスされた場所の index を保持して, operator[] または, fold が呼ばれるたびに, update を行っています.

Library Checker - Point Add Range Sum
old.yosupo.jp

終わりに

一点取得の時間計算量も O(log(N)) になりますが, 一点取得より更新の方が圧倒的に多い(体感)のと, 使い勝手を考えるとかなり便利だと思います.
バグや質問などあれば Twitter か何かにお願いします.