区间加全局求 $\max$ 是否有优于 $n\log_{2}n$ 的算法？

如果这个 $\max$ 可能的情况很少（例如值域为 $0$ 到 $3$ ）呢？