关于一种特殊的最小生成树

一个二分图，左右两部都是 $n$ 个点，有 $n^2$ 条边，支持 $O(\log n)$ 查 $i$ 到 $j,j\in[l,r]$ 的边权。

这种情况下求 MST 有没有更优的做法？