专题二 线段树

线段树

[题目][A]

敌兵布阵

题目大意：

有T组数据。
第一行为N(N <= 50000)个营地，接下来一行有N个正整数ai(第i个营地里初始为ai)(1 <= ai <= 50)，接下来每一行有一条命令。
Add i j(j <= 30)
Sub i j(j <= 30)
Query i j (i <= j)
End 结束
每组数据最多有40000条命令。
每组数据，要求输出“Case i:”和回车,对于每个Query命令，输出一个整数（询问段中的总人数，题目保证在int以内）占一行。

解题思路：

利用线段树，定义一个结构体，保存节点的l,r,value。然后建立一棵有N个节点的树。对于Add和Sub命令，即从下往上，更新每个节点的value。对于Query命令，即分区间讨论该区间和当前节点的范围关系，然后适当的把要求的范围进行划分。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn = 3*50000;//?1
typedef struct model
{
    int l,r;
    int value;
}segNODE;
segNODE segTree[maxn];
char order[10];
int num[50005];
int build(int rt,int l,int r)
{
    segTree[rt].l = l;
    segTree[rt].r = r;
    segTree[rt].value = 0;
    if(l == r)
    {
        segTree[rt].value = num[l];
        return segTree[rt].value;
    }
    else
    {
       return segTree[rt].value =  build(rt*2,l,(l+r)/2) + build(rt*2+1,(l+r)/2+1,r);
    }
}
int query(int node,int s,int e,int left,int right)
{
    int mid;
    if(left == s && right == e) return segTree[node].value;
    //if(left == right) return
    mid = (s+e)/2;
    if(mid >= left && right > mid)
    {
        return query(node*2,segTree[node*2].l,segTree[node*2].r,left,mid) + query(node*2+1,segTree[node*2+1].l,segTree[node*2+1].r,mid+1,right);
    }
    else
    {
        if(right <= mid)
            return query(node*2,segTree[node*2].l,segTree[node*2].r,left,right);
        else return query(node*2+1,segTree[node*2+1].l,segTree[node*2+1].r,left,right);
    }
}
void solve(int no,int sum,int node)
{
    segTree[node].value += sum;
    if(segTree[node].l != segTree[node].r)
    {
        if(no <= (segTree[node].l+segTree[node].r)/2) solve(no,sum,node*2);
        else solve(no,sum,node*2+1);
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int t,k = 0;
    int n;
    int i;
    int s,e;
    scanf("%d",&t);
    while(t--)
    {
        k++;
        printf("Case %d:\n",k);
        scanf("%d",&n);
        for(i = 1;i <= n;i++)
        {
            scanf("%d",&num[i]);
        }
        build(1,1,n);
        while(1)
        {
           // getchar();
            scanf("%s",order);
            //puts(order);
            //system("pause");
            if(strcmp(order,"End") == 0) break;
            scanf("%d%d",&s,&e);
            if(strcmp(order,"Query") == 0)
            {
                //printf("qqqqqq\n");
                printf("%d\n",query(1,1,n,s,e));
            }
            if(strcmp(order,"Add") == 0)
            {
                //printf("aaaaaa\n");
                solve(s,e,1);
            }
            if(strcmp(order,"Sub") == 0)
            {
                solve(s,-e,1);
            }
        }
    }
    return 0;
}