セグ木の形にして区間に辺を張るテク
頂点 +N 個
辺 +N+ElogN 個 pic.twitter.com/Xrw5y9bq2Z
— 熨斗袋 (@noshi91) 2019年11月9日

このテクニックの私なりのC++での実装例です。ご参考までに。
何か改善点がありましたらお教えいただければ幸いです。

全体像

ノードのindexは以下の図のように持っています。 $0$ と $2n$ は欠番になります。

f:id:Rorent:20200724165809p:plain:w400 — ノードのindex（n=8のとき）

以下、コードです。非再帰セグ木を理解しておく必要があるかと思います。
（非再帰セグ木未履修の方はこちらのスライドがおすすめです。）

時間計算量
頂点数を $N$ 、辺の追加回数を $Q$ とする。
グラフの初期化： $\Theta(N)$
辺の追加： $O(\log(N))$
Dijkstra法：多重辺がない場合、 $O\left({(N+Q\log(N)) \log(N)}\right)$

#include <vector>
#include <queue>
#include <limits>

using namespace std;

template<typename W>
struct range_edge_graph {
    int n;
    struct edge { int to; W weight;};
    vector<vector<edge>> g;
    
    range_edge_graph(int n) : n(n) {
        g.resize(4*n);
        for (int i = 1; i < n; ++i) {
            int cl = i<<1|0, cr = i<<1|1;
            g[i].push_back({cl, 0});
            g[i].push_back({cr, 0});
            g[cl+2*n].push_back({i+2*n, 0});
            g[cr+2*n].push_back({i+2*n, 0});
        }
        for (int i = n; i < 2*n; ++i) g[i].push_back({i+2*n, 0});
    }

    // from [l1, r1) to [l2, r2)
    void add_edge(int l1, int r1, int l2, int r2, W w) {
        int idx = g.size();
        for (l1 += n, r1 += n; l1 < r1; l1 >>= 1, r1 >>= 1) {
            if (l1 & 1) g[l1+2*n].push_back({idx, 0}), l1++;
            if (r1 & 1) --r1, g[r1+2*n].push_back({idx, 0});
        }
        vector<edge> node;
        for (l2 += n, r2 += n; l2 < r2; l2 >>= 1, r2 >>= 1) {
            if (l2 & 1) node.push_back({l2++, w});
            if (r2 & 1) node.push_back({--r2, w});
        }
        g.push_back(node);
    }

    vector<W> dijkstra(int s) {
        s += n;
        vector<W> dist(g.size(), numeric_limits<W>::max());
        dist[s] = 0;
        using P = pair<W, int>;
        priority_queue<P, vector<P>, greater<P>> que;
        que.emplace(0, s);
        while (!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if (dist[v] < p.first) continue;
            for (edge& e : g[v]) {
                if (dist[e.to] > dist[v] + e.weight) {
                    dist[e.to] = dist[v] + e.weight;
                    que.emplace(dist[e.to], e.to);
                }
            }
        }
        vector<W> res(dist.begin() + n, dist.begin() + 2*n);
        return res;
    }
};

コンストラクタについて

range_edge_graph(int n) : n(n) {

    // 1つのセグ木のサイズが2*n
    // 2つのセグ木をもつので4*n
    g.resize(4*n);

    // 辺を張る

    // まずは各セグ木内の辺から
    for (int i = 1; i < n; ++i) {

        // clは左の子の番号, crは右の子の番号
        int c1 = i<<1|0, c2 = i<<1|1;

        // 上のセグ木には根→葉方向に重み0の辺を張る
        g[i].push_back({cl, 0});
        g[i].push_back({cr, 0});

        // 下のセグ木には葉→根方向に重み0の辺を張る
        // 下のセグ木を操作したいときは +2*n すればよい
        g[cl+2*n].push_back({i+2*n, 0});
        g[cr+2*n].push_back({i+2*n, 0});
    }

    // 上のセグ木と下のセグ木の向かい合う葉同士に重み0の辺を張る
    for (int i = n; i < 2*n; ++i) g[i].push_back({i+2*n, 0});
}

区間に辺を張る部分について

// from [l1, r1) to [l2, r2)
void add_edge(int l1, int r1, int l2, int r2, W w) {

    // 下のセグ木から上のセグ木に向けて辺を持つノードを追加する

    // 追加するノードの番号
    int idx = g.size();

    // 下のセグ木の[l1, r1)に対応するノード → 追加するノード  に重み0の辺を張る
    for (l1 += n, r1 += n; l1 < r1; l1 >>= 1, r1 >>= 1) {
        if (l1 & 1) g[l1+2*n].push_back({idx, 0}), l1++;
        if (r1 & 1) --r1, g[r1+2*n].push_back({idx, 0});
    }
    
    // 追加するノードの隣接リスト 
    vector<edge> node;

    // 追加するノード → 上のセグ木の[l2, r2)に対応するノード  に重みwの辺を張る
    for (l2 += n, r2 += n; l2 < r2; l2 >>= 1, r2 >>= 1) {
        if (l2 & 1) node.push_back({l2++, w});
        if (r2 & 1) node.push_back({--r2, w});
    }

    // ノードを追加
    g.push_back(node);
}

使用例

※以下、解法のネタバレを含みます。

例1

第二回全国統一プログラミング王決定戦予選 D - Shortest Path on a Line
atcoder.jp

問題概要

$N$ 頂点からなる無向グラフがあり、存在する辺の情報が $M$ 個、以下の形式で与えられる。

$1$ 以上 $N$ 以下の整数 $L_i, R_i$ 及び正整数 $C_i$ について、 $L_i\leq s \lt t \leq R_i$ を満たすすべての整数の組 $(s, t)$ に対し、頂点 $s$ と頂点 $t$ の間に長さ $C_i$ の辺が存在する。

このグラフ上で、頂点 $1$ から頂点 $N$ までの最短路の長さを求めよ。

解法

与えられる辺の情報をわかりやすく言い換えると、区間 $[L_i, R_i+1)$ 内であればどの頂点間もコスト $C_i$ で移動できるということになりますね。
よって、上記のライブラリを用いて、区間 $[L_i, R_i+1)$ から区間 $[L_i, R_i+1)$ に重み $C_i$ の辺を張ってDijkstra法で最小コストを求めればおしまいです。このテクさえ知っていれば、何も考えずにできます。
（実はもっと賢い解法があるのですが、それに関しては解説PDFをご参照ください。）

私の提出コードです。
atcoder.jp

例2

Codeforces Round #406 (Div. 1) B. Legacy
codeforces.com

問題概要

$n$ 頂点からなる有向グラフがあり、存在する辺の情報が $q$ 個、以下の3つの形式で与えられる。

頂点 $v_i$ から頂点 $u_i$ を結ぶ、重み $w_i$ の辺

頂点 $v_i$ から区間 $[l_i, r_i$ ] のすべての頂点を結ぶ、重み $w_i$ の辺

区間 $[l_i, r_i$ ] のすべての頂点から頂点 $v_i$ を結ぶ、重み $w_i$ の辺

このグラフ上で、頂点 $s$ から各頂点への最小コストを求めよ。

解法

頂点 $v_i$ から頂点 $u_i$ 　→　区間 $[v_i, v_i+1)$ から区間 $[u_i, u_i+1)$
頂点 $v_i$ から区間 $[l_i, r_i$ ]　→　区間 $[v_i, v_i+1)$ から区間 $[l_i, r_i+1)$
区間 $[l_i, r_i$ ] から頂点 $v_i$ 　→　区間 $[l_i, r_i+1)$ から区間 $[v_i, v_i+1)$

と言い換えてしまえば、おしまいです。

私の提出コードです。
codeforces.com

他にこのテクが使えそうな問題を随時募集しています。

追記（2020/08/23）

beetさん(@beet_aizu)より、上下のセグ木の葉をくっつけてしまえばセグ木部分を $3n$ にできるというアイデアをいただきました。ありがとうございます。

range_edge_graph(int n) : n(n) {
    g.resize(3*n);
    for (int i = 1; i < n; ++i) {
        int cl = i<<1|0, cr = i<<1|1;
        add_edge(i, cl, 0);
        add_edge(i, cr, 0);
        add_edge(cl+2*n, i+2*n, 0);
        add_edge(cr+2*n, i+2*n, 0);
    }
}

// map [3n, 4n) -> [n, 2n)
void add_edge(int u, int v, W w) {
    if (3*n <= u) u -= 2*n;
    g[u].push_back({v, w});
}

// from [l1, r1) to [l2, r2)
void add_edge(int l1, int r1, int l2, int r2, W w) {
    int idx = g.size();
    for (l1 += n, r1 += n; l1 < r1; l1 >>= 1, r1 >>= 1) {
        if (l1 & 1) add_edge(l1+2*n, idx, 0), l1++;
        if (r1 & 1) --r1, add_edge(r1+2*n, idx, 0);
    }
    vector<edge> node;
    for (l2 += n, r2 += n; l2 < r2; l2 >>= 1, r2 >>= 1) {
        if (l2 & 1) node.push_back({l2++, w});
        if (r2 & 1) node.push_back({--r2, w});
    }
    g.push_back(node);
}

Lorent’s diary

区間に辺を張るテクの実装例（Dijkstra法セット）と使用例

全体像

コンストラクタについて

区間に辺を張る部分について

使用例

例1

例2

追記（2020/08/23）