~ Esoteria Algorithm in Reverse Observatory

线段树优化 Dijkstra

过早的优化是万恶之源。
Go beyond speed.

一般的 Dijkstra 使用 priority_queue 维护当前最短路的距离,但不吸氧气的 STL 性能表象不佳。维护当前最短路距离需要不断取出最小值,可以通过线段树查询最小值再修改为无穷大来模拟。

线段树

Introduction Chapter

有一类问题,数据通常可以建模到数轴或是数列上,操作一般是每次对数轴上的一个区间或是数列中的连续若干个数进行修改、查询等,数据规模往往比较大。这些数据就适合用线段树维护。