前言：

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。       对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。       使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1166

这个题直接用暴力的话，超时。

可以用，线段树，快很多，

这是我做的第一个线段树的题。

线段树可以分为几个部分

第一  建树

第二 插入数据

第三 查找数据

我的AC代码

#include<stdio.h> #include<string.h>

#define MAXSIZE 50005

struct node

{    

int left,right,sum;

} tree[MAXSIZE*4];

void build(int node,int left,int right)//建树，二分的思路

{    

tree[node].left=left;    

tree[node].right=right;   

tree[node].sum=0;    

if(left==right)       //如果左边界与右边界相等，则说明不能再二分了即就是，像一棵二叉树一样到了最低了；

return ;    

int mid=(left+right)/2;   

build(node*2,left,mid);   

build(node*2+1,mid+1,right);

}

void update(int node,int pos,int val)//插入数据，更新数据

{    

tree[node].sum+=val;    

if(tree[node].left==pos&&tree[node].right==pos)        

return ;    

int mid=(tree[node].left+tree[node].right)/2;    

if(pos<=mid)        

update(node*2,pos,val);    

else        

update(node*2+1,pos,val); }

int query(int node,int left,int right) //查找数据，

{    

if(tree[node].left==left&&tree[node].right==right)        

return tree[node].sum;    

int mid=(tree[node].left+tree[node].right)/2;    

if(right<=mid)        

return query(node*2,left,right);    

else if(left>mid)        

return query(node*2+1,left,right);    

else        

return query(node*2,left,mid)+query(node*2+1,mid+1,right);

}

int main(void)

{    

int t,n,k,i;    

int x,y,c;    

char s[20];    

scanf("%d",&t);    

k=0;    

while(t--)    

{        

scanf("%d",&n);        

build(1,1,n);        

printf("Case %d:\n",++k);        

for(i=1; i<=n; i++)        

{            

scanf("%d",&c);            

update(1,i,c);        

}        

while(scanf("%s",s)==1&&s[0]!=‘E‘)        

{            

scanf("%d%d",&x,&y);            

if(s[0]==‘Q‘)            

{                

printf("%d\n",query(1,x,y));            

}            

else if(s[0]==‘A‘)            

{                

update(1,x,y);           

 }            

else if(s[0]==‘S‘)            

{                

update(1,x,-y);            

}        

}    

}    

return  0;

}

网上代码

#include <stdio.h> #include <string.h> #define MAXSIZE 50001

struct node {     int left, right ;     int sum ; }tree[MAXSIZE * 4];

int     tcase, n ;

void build (int node, int left, int right) {     tree[node].left     = left ;     tree[node].right    = right ;     tree[node].sum      = 0 ;     if (left == right)         return ;     int mid = (left + right) / 2 ;     build (node * 2, left, mid) ;     build (node * 2 + 1, mid + 1, right) ; }

void update (int node, int pos, int val) {     // 当前区间的总人数增加     tree[node].sum += val ;     // 刚好走到第pos 个营地所在的叶子     if (tree[node].left == pos &&tree[node].right == pos)     {         return ;     }     int mid = (tree[node].left + tree[node].right) / 2 ;     // 若营地在当前区间的左半边     if (pos <= mid)         update (node * 2, pos, val) ;     // 若营地在当前区间的右半边     else         update (node * 2 + 1, pos, val) ; }

int query (int node, int left, int right) {     // 若区间刚好匹配     if (tree[node].left == left &&tree[node].right == right)         return tree[node].sum ;

    // 若区间无交集     //if (tree[node].left > right ||tree[node].right < left)         //return 0 ;

    // 若区间有交集     int mid = (tree[node].left + tree[node].right) / 2 ;

    // 若查询区间在左半边     if (right <= mid)         return query (node * 2, left, right) ;     // 若查查询区间在右半边     else if (mid < left)         return query (node * 2 + 1, left, right) ;     // 若查询区间横跨当前区间的中点     else         return query (node * 2, left, mid) + query (node * 2 + 1, mid + 1, right) ; }

int main () {     char    str[20] ;     int     i, j ;     int     x, y ;

    while (scanf ("%d", &tcase) != EOF)     {         for (j = 1 ; j <= tcase ; ++j)         {             scanf ("%d", &n) ;             build (1, 1, n) ;             for (i = 1 ; i <= n ; ++i)             {                 scanf ("%d", &x) ;                 // 从根部开始查找，第i 个营地的值增加x                 update (1, i, x) ;             }             printf ("Case %d:\n", j) ;             while (scanf ("%s", str), *str != ‘E‘)             {                 scanf ("%d%d", &x, &y) ;                 if (*str == ‘Q‘)                     printf ("%d\n", query (1, x, y)) ;                 else if (*str == ‘A‘)                     update (1, x, y) ;                 else if (*str == ‘S‘)                     update (1, x, -y) ;             }         }     }     return 0 ; }

HDU-1166-敌兵布阵（线段树）