题目描述（POJ3264）： 每天挤奶时，约翰的 N 头奶牛（1≤ N ≤50,000）都以相同的顺序排队。他挑选一系列连续的奶牛来玩游戏。为了让所有奶牛都玩得开心，它们的高度差异不应太大。约翰列出了 Q 组（1≤ Q ≤200,000）奶牛和它们的高度（1≤height≤1,000,000）。他希望确定每个小组中最高和最矮的奶牛之间的高度差异。

输入： 第1行包含两个整数 N 和 Q 。接下来 N 行，每行都包含一个整数，表示奶牛的高度。最后 Q 行，每行都包含两个整数 A 和 B （1≤ A ≤ B ≤ N ），代表从 A 到 B 的奶牛范围。

输出： 输出 Q 行，每行都包含一个整数，表示该范围内最高和最矮奶牛的高度差。

题解： 本题求解区间最大值和最小值之差，是典型的RMQ问题，可以使用ST解决。

1. 算法设计

（1）创建ST。

（2）查询[ a , b ]区间的最大值和最小值，然后输出其差值。 c2s40m3/008Sh8sCuUYX45NublNJqmRkq8dhLCO8NJUB9112Dzn3/aWcWpDZmaMo

2. 算法实现