转:

线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2,b]。

这里有说明：
http://blog.csdn.net/oopos

线段树是一种特殊的二叉树，它的每个结点放的是线段（即线段的两个端点）

还是不懂[em15][em18]

给你看个ACM的线段树的题目吧(zju-1610)
#include <stdio.h>
#include "stdlib.h"

int que[8005];

typedef struct
{
    int left;
    int right;
    int cor;
    int lson, rson;
}node;
node tree[20005];
int now;

int addr;

void init()
{

    now = 1;
}

int cmp(const void *a, const void *b)
{

    int ans = 0;
    int ta = *(int *)a;
    int tb = *(int *)b;
    if (tree[ta].cor<tree[tb].cor)
    {
        ans = -1;
    }
    else
    {
        if (tree[ta].cor>tree[tb].cor)
        {
            ans = 1;
        }
        else
        {
            if (tree[ta].left<tree[tb].left)
            {
                ans = -1;
            }
            else
            {
                if (tree[ta].left>tree[tb].left)
                {
                    ans = 1;
                }
            }
        }
    }
    return ans;
}

void creat_tree(int l, int r, int p)
{

    tree[p].left = l;
    tree[p].right = r;
    tree[p].cor = -1;
    tree[p].lson = -1;
    tree[p].rson = -1;
    if (l<r-1)
    {
        tree[p].lson = now++;
        creat_tree(l, (l+r)/2, tree[p].lson);
        tree[p].rson = now++;
        creat_tree((l+r)/2, r, tree[p].rson);
    }
}

void insert(int l, int r, int c, int p)
{

    int middle = ( tree[p].left+tree[p].right ) / 2;
    if (tree[p].cor==c)
    {
        return;
    }
    if (tree[p].left==l && tree[p].right==r)
    {
        tree[p].cor = c;
        return;
    }
    if (tree[p].cor!=-2)
    {
        tree[tree[p].lson].cor = tree[p].cor;
        tree[tree[p].rson].cor = tree[p].cor;
        tree[p].cor = -2;
    }
    if (l>=middle)
    {
        insert(l, r, c, tree[p].rson);
        return;
    }
    if (r<=middle)
    {
        insert(l, r, c, tree[p].lson);
        return;
    }
    insert(l, middle, c, tree[p].lson);
    insert(middle, r, c, tree[p].rson);
}

void cup(int p)
{

    if (tree[p].cor==-2)
    {
        cup(tree[p].lson);
        cup(tree[p].rson);
    }
    else
    {
        if (tree[p].cor!=-1)
        {
            que[addr++] = p;
        }
    }
}

int main()
{

    int n;
    int a, b, c;
    int i;
    int count ;
    while (scanf("%d", &n) != EOF)
    {
        init();
        creat_tree(0, 8000, 0);
        for (i=0; i<n; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            insert(a, b, c, 0);
        }
        addr = 0;
        cup(0);
        qsort(que, addr, sizeof(int), cmp);
        count = 1;
        for (i=1; i<addr; i++)
        {
            if (tree[que[i]].cor!=tree[que[i-1]].cor)
            {
                printf("%d %d\n", tree[que[i-1]].cor, count);
                count = 1;
            }
            else
            {
                if (tree[que[i]].left!=tree[que[i-1]].right)
                {
                    count ++;
                }
            }
        }
        printf("%d %d\n", tree[que[i-1]].cor, count);
        printf("\n");
    }
    return 0;
}

线段树的测度非常灵活，可以按需设定，这样增大了线段树的适用范围