這是我寫(xiě)的第一道線段樹(shù)，思路還算清晰，不過(guò)之前走了不少?gòu)澛贰?br />主要錯(cuò)在：誤以為線段樹(shù)是一棵滿二叉樹(shù)，建樹(shù)時(shí)吃了苦頭。//線段樹(shù)除了最后一層可能不滿足滿二叉樹(shù)性質(zhì)外，上面的所有層構(gòu)成完全二叉樹(shù)，因此仍然可以用滿二叉樹(shù)的性質(zhì)：如果樹(shù)根節(jié)點(diǎn)從1開(kāi)始編號(hào)，則對(duì)任意編號(hào)的節(jié)點(diǎn)t，左子樹(shù)編號(hào)為t*2，右子樹(shù)編號(hào)為t*2+1，父節(jié)點(diǎn)編號(hào)為t/2。這樣，建樹(shù)的時(shí)候節(jié)點(diǎn)內(nèi)就不用記錄兒子或父節(jié)點(diǎn)的信息了。
下面結(jié)合poj3264說(shuō)一下我對(duì)線段樹(shù)的理解。
題意描述：隨即給定N個(gè)奶牛（<=50000）的身高，奶牛按輸入順序編號(hào)，接下來(lái)

有Q次（<=2E5）查詢，每次查詢時(shí)給定兩個(gè)編號(hào)a,b，要求給出編號(hào)在[a, b]之間

奶牛的身高最大差值。
要用線段樹(shù)的原因很明顯，線性查找一定超時(shí)。
下面是我的解題思路：
建樹(shù)：
建樹(shù)過(guò)程很簡(jiǎn)單，先建左右子樹(shù)，再建雙親。注意節(jié)點(diǎn)中信息的更新。
查詢：
查詢過(guò)程可分為四種情況
假設(shè)節(jié)點(diǎn)表示的區(qū)間為[a, b]，要查詢的區(qū)間為[aa, bb]，mid = (a+b)/2.
情況1.[aa, bb]區(qū)間正好是[a,b]區(qū)間。
情況2.[aa, bb]區(qū)間在[a, mid]區(qū)間內(nèi)。
情況3.[aa, bb]區(qū)間在[mid+1, b]區(qū)間內(nèi)。
情況3.[aa, bb]區(qū)間一部分在[a, mid]區(qū)間內(nèi)，一部分在[mid+1, b]區(qū)間內(nèi)。這種情況下需要有合并過(guò)程。也就通過(guò)比較從兩部分中選出min和max。
一些細(xì)節(jié)：據(jù)說(shuō)動(dòng)態(tài)分配內(nèi)存可能超時(shí)，所以這里用了一個(gè)數(shù)組A[]來(lái)作為開(kāi)辟空間的區(qū)域。
以下是本題的代碼：

#include<stdio.h>
#include<stdlib.h>
#define LEN 50010
#define LEN0 2700000 //把數(shù)組開(kāi)到最大，有內(nèi)存不用浪費(fèi)。
typedef struct
{
    int min, max;
    int l, r;
    int a, b;
}Node;
int count; //指向A[]中當(dāng)前可用空間
Node A[LEN0];
int h[LEN];//奶牛身高
int small(int a, int b)
{
    if(a < b)
        return a;
    return b;
}
int big(int a, int b)
{
    if(a > b)
        return a;
    return b;
}
void MakeTree(int i)
{
    int a = A[i].a;
    int b = A[i].b;
    int mid = (a + b) / 2;
    if(a == b)//這個(gè)節(jié)點(diǎn)是葉子
    {
        A[i].min = A[i].max = h[a];
        return;
    }
    int l = ++count;//開(kāi)辟空間
    int r = ++count;
    A[l].a = a;
    A[l].b = mid;
    A[r].a = mid + 1;
    A[r].b = b;
    MakeTree(l);//建立左子樹(shù)
    MakeTree(r);//建立右子樹(shù)
    A[i].min = small(A[l].min, A[r].min);//更新雙親節(jié)點(diǎn)
    A[i].max = big(A[l].max, A[r].max);
    A[i].l = l;
    A[i].r = r;
}
Node Query(int t, int aa, int bb)
{
    int a = A[t].a;
    int b = A[t].b;
    if(a == aa && b == bb)//情況1
    {
        return A[t];
    }
    int mid = (a + b) / 2;
    if(bb <= mid)//情況2
        return Query(A[t].l, aa, bb);
    if(aa >= mid + 1)//情況3
        return Query(A[t].r, aa, bb);
    int n1 = ++count;
    int n2 = ++count;
    A[n1] = Query(A[t].l, aa, mid);//情況4
    A[n2] = Query(A[t].r, mid + 1, bb);
    A[n1].min = small(A[n1].min, A[n2].min);//合并過(guò)程
    A[n1].max = big(A[n1].max, A[n2].max);
    --count;
    --count;
    return A[n1];
}
int main()
{
    int i, j;
    int N, Q;
    int a, b;
    scanf("%d%d", &N, &Q);
    for(i = 1; i <= N; i++)
        scanf("%d", &h[i]);
    count = 0;
    int t = ++count;
    A[t].a = 1;
    A[t].b = N;
    MakeTree(t);
    for(i = 0; i < Q; i++)
    {
        scanf("%d%d", &a, &b);
        A[0] = Query(1, a, b);
        printf("%d\n", A[0].max - A[0].min);
    }
    //system("pause");
} 

下面是利用了滿二叉樹(shù)性質(zhì)的代碼：（同樣的代碼用java就超時(shí)，C++ 1563MS AC，java和C++的效率差距真的有這么大嗎）

利用滿二叉樹(shù)性質(zhì)的代碼
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#define LEN 400020
#define max(a, b) (a) > (b) ? (a) : (b)
#define min(a, b) (a) < (b) ? (a) : (b)
typedef struct Node
{
    int bg, ed;
    int tl, st;
}Node;
Node nds[400020];
int tals[200020];
int maxv;
int minv;
 void query(int t, int bg, int ed){
    if(nds[t].bg == bg && nds[t].ed == ed){
        if(maxv < nds[t].tl)
            maxv = nds[t].tl;
        if(minv > nds[t].st)
            minv = nds[t].st;
        return;
    }
    int mid = (nds[t].bg + nds[t].ed) >> 1;
    if(ed <= mid){
        query(t << 1, bg, ed);
    }
    else if(bg > mid){
        query((t << 1) + 1, bg, ed);
    }
    else{
        query(t << 1, bg, mid);
        query((t << 1) + 1, mid + 1, ed);
    }
        
    }
void makeTree(int t)
{
    int bg = nds[t].bg;
    int ed = nds[t].ed;
    if(bg == ed){
        nds[t].tl = tals[bg];
        nds[t].st = tals[bg];
        return;
    }
    int lf = t << 1;
    int rt = lf + 1;
    int mid = (bg + ed) >> 1;
    
    nds[lf].bg = bg;
    nds[lf].ed = mid;
    makeTree(lf);
    nds[rt].bg = mid + 1;
    nds[rt].ed = ed;
    makeTree(rt);
    
    nds[t].tl = max(nds[lf].tl, nds[rt].tl);
    nds[t].st = min(nds[lf].st, nds[rt].st);
}
int main()
{
    
    int i, j;
    int N, Q;
    int a, b;
    scanf("%d%d", &N, &Q);
    
    for(int i = 1; i <= N; i++)
    {
        scanf("%d", &tals[i]);
    }
    nds[1].bg = 1;
    nds[1].ed = N;
    makeTree(1);
    for(int i = 0; i < Q; i++)
    {
        scanf("%d%d", &a, &b);
        maxv = INT_MIN;
        minv = INT_MAX;
        query(1, a, b);
        printf("%d\n", maxv - minv);
    }
    
    return 0;
}

Java的超時(shí)代碼
import java.util.*;
import java.util.Scanner;

class Main {
    
    static Node nds[] = new Node[400020];
    static int[] tals = new int[200020];
    static int max;
    static int min;
    static{
        for(int i = 0; i < 400020; i++)
            nds[i] = new Node(0, 0);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Q = sc.nextInt();
        for(int i = 1; i <= N; i++)
        {
            tals[i] = sc.nextInt();
        }
        nds[1].bg = 1;
        nds[1].ed = N;
        makeTree(1);
        for(int i = 0; i < Q; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            max = Integer.MIN_VALUE;
            min = Integer.MAX_VALUE;
            
            query(1, a, b);
            System.out.println((max - min));
        }
    }
    
    static void query(int t, int bg, int ed){
        if(nds[t].bg == bg && nds[t].ed == ed){
            if(max < nds[t].tl)
                max = nds[t].tl;
            if(min > nds[t].st)
                min = nds[t].st;
            return;
        }
        int mid = (nds[t].bg + nds[t].ed) / 2;
        if(ed <= mid){
            query(t * 2, bg, ed);
        }
        else if(bg > mid){
            query(t * 2 + 1, bg, ed);
        }
        else{
            query(t * 2, bg, mid);
            query(t * 2 + 1, mid + 1, ed);
        }
        
    }
    static void makeTree(int t){
        int bg = nds[t].bg;
        int ed = nds[t].ed;
        if(bg == ed){
            nds[t].tl = tals[bg];
            nds[t].st = tals[bg];
            return;
        }
        int lf = t * 2;
        int rt = lf + 1;
        int mid = (bg + ed) / 2;
        
        nds[lf].bg = bg;
        nds[lf].ed = mid;
        makeTree(lf);
        nds[rt].bg = mid + 1;
        nds[rt].ed = ed;
        makeTree(rt);
        
        nds[t].tl = Math.max(nds[lf].tl, nds[rt].tl);
        nds[t].st = Math.min(nds[lf].st, nds[rt].st);
    }
}
class Node{
    int bg, ed;
    int tl, st;
    public Node(int tl, int st){
        this.tl = tl;
        this.st = st;
    }
}