2017-09-07から1日間の記事一覧

永続segtree

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