其实这个的标题叫 平凡线段树上二分幻术，因为这是一个民科在乱叫。

如标题所言，这个东西确实非常 trivial。碍于网络上没有一个成体系的文章供参考就只能自己来炒炒冷饭。

如果出了什么 bug 就当个笑话看。

我们这样来描述一类问题

给出一个序列 $\{a_n\}$ 以及函数 $\textbf{f}(x)\in\{0,1\}$，在 $[l,r]$ 中查找满足 $\textbf{f}(a_i)=1$ 的所有位置所组成的集合中的一个元素，该元素满足某个指定的性质。

网络上大部分资料对这类问题的线段树二分做法只停留在全局查询。事实上，线段树二分的做法完全可以搬到区间上，做法并不困难。

以下令 $[l,r]$ 为线段树执行时的当前区间，$[x,y]$ 为询问区间。

我们在执行线段树的时候，维护一个标记 $g\in\{0,1\}=[[l,r]\subseteq[x,y]]$，如果为 $0$，则继续在线段树上搜寻询问区间，否则就执行二分，因为查询的结点数为 $\Theta(\log_2 n)$ 且树的深度为 $\Theta(\log_2 n)$，所以单次复杂度 $\Theta(\log_2 n)$。

例题大概是 codeforces - 407E，我负责给李涵口胡，然后李涵就把代码杠出来了。