这是我写的第一道线段树，思路还算清晰，不过之前走了不少弯路。
主要错在：误以为线段树是一棵满二叉树，建树时吃了苦头。//线段树除了最后一层可能不满足满二叉树性质外，上面的所有层构成完全二叉树，因此仍然可以用满二叉树的性质：如果树根节点从1开始编号，则对任意编号的节点t，左子树编号为t*2，右子树编号为t*2+1，父节点编号为t/2。这样，建树的时候节点内就不用记录儿子或父节点的信息了。
下面结合poj3264说一下我对线段树的理解。
题意描述：随即给定N个奶牛（<=50000）的身高，奶牛按输入顺序编号，接下来

有Q次（<=2E5）查询，每次查询时给定两个编号a,b，要求给出编号在[a, b]之间

奶牛的身高最大差值。
要用线段树的原因很明显，线性查找一定超时。
下面是我的解题思路：
建树：
建树过程很简单，先建左右子树，再建双亲。注意节点中信息的更新。
查询：
查询过程可分为四种情况
假设节点表示的区间为[a, b]，要查询的区间为[aa, bb]，mid = (a+b)/2.
情况1.[aa, bb]区间正好是[a,b]区间。
情况2.[aa, bb]区间在[a, mid]区间内。
情况3.[aa, bb]区间在[mid+1, b]区间内。
情况3.[aa, bb]区间一部分在[a, mid]区间内，一部分在[mid+1, b]区间内。这种情况下需要有合并过程。也就通过比较从两部分中选出min和max。
一些细节：据说动态分配内存可能超时，所以这里用了一个数组A[]来作为开辟空间的区域。
以下是本题的代码：

#include<stdio.h>
#include<stdlib.h>
#define LEN 50010
#define LEN0 2700000 //把数组开到最大，有内存不用浪费。
typedef struct
{
    int min, max;
    int l, r;
    int a, b;
}Node;
int count; //指向A[]中当前可用空间
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)//这个节点是叶子
    {
        A[i].min = A[i].max = h[a];
        return;
    }
    int l = ++count;//开辟空间
    int r = ++count;
    A[l].a = a;
    A[l].b = mid;
    A[r].a = mid + 1;
    A[r].b = b;
    MakeTree(l);//建立左子树
    MakeTree(r);//建立右子树
    A[i].min = small(A[l].min, A[r].min);//更新双亲节点
    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);//合并过程
    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");
} 

下面是利用了满二叉树性质的代码：（同样的代码用java就超时，C++ 1563MS AC，java和C++的效率差距真的有这么大吗）

利用满二叉树性质的代码
#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的超时代码
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;
    }
}