HDU 1166 敌兵布阵 (树状数组和线段树解法)

题目: 戳我

树状数组code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;
#define clc(a, b) memset(a, b, sizeof(a))
const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 5e4+5;

int c[maxn], n;

int lowbit(int x)
{
    return x&-x;
}

void add(int x, int val)
{
    while(x<=n)
    {
        c[x] += val;
        x += lowbit(x);
    }
}

int query(int l, int r)
{
    int sum1 = 0, sum2 = 0;
    while(r > 0)
    {
        sum1 += c[r];
        r -= lowbit(r);
    }
    l = l-1;
    while(l > 0)
    {
        sum2 += c[l];
        l -= lowbit(l);
    }
    return sum1-sum2;
}

int main()
{
    int T, x, l, r;
    char q[100];
    scanf("%d", &T);
    for(int t = 1; t <= T; t++)
    {
        scanf("%d", &n);
        clc(c, 0);
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &x);
            add(i+1, x);
        }
        printf("Case %d:
", t);
        while(true)
        {
            scanf(" %s", q);
            if(!strcmp(q, "End")) break;
            if(!strcmp(q, "Query"))
            {
                scanf("%d %d", &l, &r);
                printf("%d
", query(l, r));
            }
            else if(!strcmp(q, "Sub"))
            {
                scanf("%d %d", &l, &x);
                add(l, -x);
            }
            else
            {
                scanf("%d %d", &l, &x);
                add(l, x);
            }
        }
    }
    return 0;
}

线段树code:

线段树代码太长===

#include <stdio.h>
#include <string.h>
int a[50010];
struct node
{
    int left,right,sum;
}b[150010];
 
 
void build(int left,int right,int i)
{
    int mid;
    b[i].left=left;
    b[i].right=right;
    if(left==right)
    {
        b[i].sum = a[left];
        return ;
    }
 
    mid=(left+right)/2;
    build(left,mid,2*i);
    build(mid+1,right,2*i+1);
    b[i].sum=b[2*i].sum+b[2*i+1].sum;
 
}
 
void  Add(int id,int num,int i)
{
    if(b[i].left==b[i].right)
    {
        b[i].sum=b[i].sum+num;
        return ;
    }
    else
    {
        b[i].sum=b[i].sum+num;
        if(id<=b[i*2].right) Add(id,num,2*i);
        else Add(id,num,2*i+1);
    }
}
 
 
int Query(int left, int right,int i)
{
    int mid;
    if(b[i].left==left && b[i].right ==right) return b[i].sum;
    mid=(b[i].left+b[i].right)/2;
    if(right<=mid) return Query(left,right,2*i);
    else if (left>mid ) return Query(left,right,2*i+1);
    else return Query(left,mid,2*i) + Query(mid+1,right,2*i+1);
}
 
 
int main()
{
    int Case;
    int n;
    char str[10];
    scanf("%d",&Case);
    int id,num;
    int i;
    int k=1;
    while(Case--)
    {
 
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        build(1,n,1);
        printf("Case %d:
",k++);
        while(1)
        {
 
            scanf("%s",str);
            if(strcmp(str,"End")==0) break;
            scanf("%d%d",&id,&num);
            if(strcmp(str,"Query")==0)
            {
                printf("%d
",Query(id,num,1));
            }
            if(strcmp(str,"Add")==0)
            {
                //scanf("%d%d",&id,&num);
                Add(id,num,1);
            }
            if(strcmp(str,"Sub")==0)
            {
                //scanf("%d%d",&id,&num);
                Add(id,-num,1);
            }
        }
    }
    return 0;
}