区间查询（树状数组之差点问线问题）

缺乏、安全感 2022-08-05 13:08 174阅读 0赞

## 1110: 区间查询 ##

**时间限制: **2 Sec

**内存限制: **32 MB

**提交: **162

**解决: **62

[提交][Link 1] [状态][Link 2]

### 题目描述 ###

食堂有N个打饭窗口，现在正到了午饭时间，每个窗口都排了很多的学生，而且每个窗口排队的人数在不断的变化。  
现在问你第i个窗口到第j个窗口一共有多少人在排队？

### 输入 ###

输入的第一行是一个整数T，表示有T组测试数据。  
每组输入的第一行是一个正整数N（N<=30000），表示食堂有N个窗口。  
接下来一行输入N个正整数，第i个正整数ai表示第i个窗口最开始有ai个人排队。（1<=ai<=50）  
接下来每行有一条命令，命令有四种形式：  
(1)Add i j，i和j为正整数，表示第i个窗口增加j个人（j不超过30）；  
(2)Sub i j，i和j为正整数，表示第i个窗口减少j个人（j不超过30）；  
(3)Query i j，i和j为正整数，i<=j，表示询问第i到第j个窗口的总人数；  
(4)End 表示结束，这条命令在每组数据最后出现；  
每组数据最多有40000条命令。

### 输出 ###

对于每组输入，首先输出样例号，占一行。  
然后对于每个Query询问，输出一个整数，占一行，表示询问的段中的总人数，这个数保持在int以内。

### 样例输入 ###

1101 2 3 4 5 6 7 8 9 10Query 1 3Add 3 6Query 2 7Sub 10 2Add 6 3Query 3 10End

### 样例输出 ###

Case 1:63359

### 提示 ###

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int n,c1[30010];
    int lowbit(int n)
    {
        return n&(-n);
    }
    int add(int i,int data)
    {
        while(i<=n)
        {
            c1[i]+=data;
            i+=lowbit(i);
        }
    }
    long long sum(int i)
    {
        long long sum1=0;
        while(i>0)
        {
            sum1+=c1[i];
            i-=lowbit(i);
        }
        return sum1;
    }
    int main()
    {
        int times,i,b,d,a,f=1;
        char c[20];
        cin>>times;
        while(times--)
        {
            memset(c1,0,sizeof(c1));
            cin>>n;
            cout<<"Case "<<f++<<":"<<endl;
            for(i=1;i<=n;i++)
            {
                cin>>a;
                add(i,a);
            }
            while(cin>>c)
            {
                if(strcmp(c,"End")==0)
                {
                    break;
                }
                else if(strcmp(c,"Add")==0)
                {
                        cin>>b>>d;
                        add(b,d);
                }
                else if(strcmp(c,"Sub")==0)
                {
                    cin>>b>>d;
                    add(b,-d);
                }
                else
                {
                    cin>>b>>d;
                    cout<<sum(d)-sum(b-1)<<endl;
                }
            }
        }
    }

[Link 1]: http://arena.acmclub.com/submitpage.php?id=1110
[Link 2]: http://arena.acmclub.com/problemstatus.php?id=1110