分类 树状数组 下的文章

原题链接

HDU1166


题目抽象

给出一串数,要求
1)单点加减修改
2)区间查询


做法

树状数组,线段树,zkw。
尤其:如果常数不能像我的一样小,请用特技(scanf)。


代码

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

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

const int maxn = 5e4 + 10;
int a[maxn];
int n;

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

int query(int x)
{
    int ans = 0;
    while(x > 0)
    {
        ans += a[x];
        x -= lowbit(x);
    }
    return ans;
}

int main()
{
    int t;
    cin>>t;
    for(int i = 1; i <= t; i++)
    {
        cout<<"Case "<<i<<":"<<endl;
        memset(a, 0, sizeof a);
        cin>>n;
        for(int j = 1; j <= n; j++)
        {
            int tmp;
            cin>>tmp;
            add(j, tmp);
        }
        string type;
        while(cin>>type && type != "End")
        {
            if(type == "Add")
            {
                int x, v;
                cin>>x>>v;
                add(x, v);
            }
            else if(type == "Sub")
            {
                int x, v;
                cin>>x>>v;
                add(x, -v);
            }
            else if(type == "Query")
            {
                int x, y;
                cin>>x>>y;
                cout<<query(y)-query(x-1)<<endl;
            }
        }
    }
    return 0;
}