Persistant Data Structure
永続は怖いイメージがあると思いますが、segtreeくらいなら簡単に永続化できます。 単にupdateされる予定のnodeを複製して、その複製されたnodeに対してupdateを行えばいいです。 普通のセグ木に複製してリンクを張り替えるコストが増えただけで更新の計算量…
永続は怖いイメージがあると思いますが、segtreeくらいなら簡単に永続化できます。 単にupdateされる予定のnodeを複製して、その複製されたnodeに対してupdateを行えばいいです。 普通のセグ木に複製してリンクを張り替えるコストが増えただけで更新の計算量…