題目：

輸入兩個(gè)數(shù)（m,n）,m表示牛的頭數(shù)，n表示查詢的個(gè)數(shù)。查詢時(shí)輸入兩個(gè)數(shù)（x,y），表示查詢范圍的起始值和終止值，查詢結(jié)果是，這個(gè)區(qū)間內(nèi)牛重量的最大值減去牛重量的最小值，數(shù)量級為1000,000 設(shè)計(jì)每次查詢的復(fù)雜度為logm。

例如，

輸入：

6 31734251 54 62 2

輸出：

630

分析：這道題是典型的空間換時(shí)間的題。一看到是區(qū)間的查找，我們應(yīng)該想到線段樹，這里有一篇我覺得寫得挺好的介紹線段樹的博客和大家分享一下：http://m.survivalescaperooms.com/shuaiwhu/archive/2012/04/22/2464583.html。

1.根據(jù)輸入m值，建立線段樹。public void buildTree(int m) 

2.根據(jù)輸入的牛的體重，初始化線段樹。public void initTree(SNode sn, int value)

3.根據(jù)查詢，查詢線段樹。public void find(SNode sn, int a, int b)

首先我們來看建立線段樹。由于要查詢的是最大值與最小值之差，所以在線段樹中每個(gè)結(jié)點(diǎn)除了要存儲(chǔ)范圍的左右閾值和左右子節(jié)點(diǎn)的引用外，還要存儲(chǔ)該區(qū)間內(nèi)的最大值最小值。以6頭牛為例，設(shè)編號為1-6，那么最終構(gòu)建的線段樹應(yīng)該如下圖所示：

分析一下建樹的遞歸過程。

首先，終止條件是：first==last（以結(jié)點(diǎn)1為例，那么，first=1，last=1）；

然后，遞歸的共同操作是：為結(jié)點(diǎn)中的first和last賦值，表明結(jié)點(diǎn)的范圍，即

node.first = first，node.last = last；

接著，看遞歸的參數(shù)：通過前面的分析可知，肯定有一個(gè)結(jié)點(diǎn)引用的參數(shù)node，然后因該要有結(jié)點(diǎn)的范圍，即first和last；

最后，看遞歸的過程：遞歸的過程無非就是左右子樹遞歸，即：

node.left = new SNode();node.right = new SNode();build(node.left, first, ( first + last) / 2);build(node.right, ( first + last) / 2 + 1, last);

在這里注意：為什么要先給左右子節(jié)點(diǎn)的引用賦值，因?yàn)樵?a href="http://m.survivalescaperooms.com/article.asp?typeid=160">java中，不先給賦值的話，沒有分配指向的地址，參數(shù)傳遞之后，是對參數(shù)進(jìn)行的賦值，返回之后原結(jié)點(diǎn)還是指向null的。下圖分析這個(gè)值傳遞的過程：

node1先new的過程就相當(dāng)于node1先指向了堆中的node，然后，node1拷貝到node2，node2也指向node，那么用node2修改node和node1修改node就是一樣的效果。

理解了建立線段樹的過程，后面初始化線段樹和查找的過程也是類似的方法，這里就不詳述了，直接上代碼吧。

代碼：

package study;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/** * http://poj.org/PRoblem?id=3264

 * 輸入兩個(gè)數(shù)（m,n）,m表示牛的頭數(shù)，n表示查詢的個(gè)數(shù)。 * 查詢結(jié)構(gòu)如下（x,y），這個(gè)區(qū)間內(nèi)牛重量的最大值減去，牛重量的最小值，為查詢結(jié)果， 數(shù)量級為100,0000 設(shè)計(jì)每次查詢的復(fù)雜度為logm。 *  * @author cnx * @CreateDate ; 2014年9月28日 下午9:38:25 */public class SegmentTree {    public static void main(String[] args) throws IOException {        SegmentTree s = new SegmentTree();        BufferedReader stdin = new BufferedReader(new InputStreamReader(                System.in));        String line = stdin.readLine();        StringTokenizer st = new StringTokenizer(line);        s.m = Integer.parseInt(st.nextToken());        s.n = Integer.parseInt(st.nextToken());        //建樹，并初始化結(jié)點(diǎn)        s.buildTree(s.m);        for (s.inc = 1; s.inc <= s.m; s.inc++) {            line = stdin.readLine();            st = new StringTokenizer(line);            int value = Integer.parseInt(st.nextToken());            s.initTree(s.sn, value);        }        //輸入查詢，并給出結(jié)果        for (int i = 0; i < s.n; i++) {            line = stdin.readLine();            st = new StringTokenizer(line);            int a = Integer.parseInt(st.nextToken());            int b = Integer.parseInt(st.nextToken());            s.max = 0;            s.min = 99999999;            s.find(s.sn,a,b);                        System.out.println(s.max-s.min);        }                    }    public int m;    public int n;    public SNode sn = new SNode();        public int inc;    public int max;    public int min;        /**     * 線段樹結(jié)點(diǎn)類     * @author cnx     * @CreateDate ; 2014年9月29日 上午9:17:55     */    public static class SNode {        int first;        int last;        int max;        int min = 9999999;        SNode left ;        SNode right ;    }    /**     * 構(gòu)建線段樹     * @param m  范圍為1-m     */    public void buildTree(int m) {        build(sn, 1, m);    }    /**     * 構(gòu)建線段樹的遞歸函數(shù)     * @param node     * @param L   線段樹結(jié)點(diǎn)中的first，即范圍的左閾值     * @param R   結(jié)點(diǎn)中的last，即范圍的右閾值     */    public void build(SNode node, int L, int R) {        if(node == null)            node = new SNode();        node.first = L;        node.last = R;        if (L == R) {            return;        }                node.left = new SNode();        node.right = new SNode();        build(node.left, L, (L + R) / 2);        build(node.right, (L + R) / 2 + 1, R);    }    /**     * 給線段樹的max和min字段賦值     * @param sn     * @param value  輸入的值     */    public void initTree(SNode sn, int value) {        if (value > sn.max) {            sn.max = value;        }        if (value < sn.min) {            sn.min = value;        }        if (sn.first == sn.last) {            return;        }        if (inc > (sn.last + sn.first) / 2) {            initTree(sn.right, value);        } else {            initTree(sn.left, value);        }    }    /**     * 在線段樹中查找，范圍a-b的最大值和最小值     * @param sn     * @param a     * @param b     */    public void find(SNode sn, int a, int b){                if (sn.first==a && sn.last==b) {            if (sn.max>max) {                max = sn.max;            }            if (sn.min<min) {                min = sn.min;            }            return;        }                if (b<=(sn.first+sn.last)/2) {            find(sn.left, a, b);        }        else if (a>(sn.first+sn.last)/2) {            find(sn.right, a, b);        }        else {            find(sn.left, a, (sn.first+sn.last)/2);            find(sn.right, (sn.first+sn.last)/2+1, b);        }    }}