POJ 3468 A Simple Problem with Integers （树状数组成段更新）

梦里梦外; 2022-06-12 04:40 85阅读 0赞

Let A1, A2, ... , AN be N elements. You need to deal with two kinds of operations. One type of operation is to add a given number to a few numbers in a given interval. The other is to query the value of some element.

Input

There are a lot of test cases.  
The first line contains an integer N. (1 <= N <= 50000)  
The second line contains N numbers which are the initial values of A1, A2, ... , AN. (-10,000,000 <= the initial value of Ai <= 10,000,000)  
The third line contains an integer Q. (1 <= Q <= 50000)  
Each of the following Q lines represents an operation.  
"1 a b k c" means adding c to each of Ai which satisfies a <= i <= b and (i - a) % k == 0. (1 <= a <= b <= N, 1 <= k <= 10, -1,000 <= c <= 1,000)  
"2 a" means querying the value of Aa. (1 <= a <= N)

Output

For each test case, output several lines to answer all query operations.

Sample Input

4 
    1 1 1 1
    14
    2 1
    2 2
    2 3
    2 4
    1 2 3 1 2
    2 1 
    2 2
    2 3
    2 4
    1 1 4 2 1
    2 1
    2 2
    2 3
    2 4

Sample Output

1
    1
    1
    1
    1
    3
    3
    1
    2
    3
    4
    1

题解：

这题好难啊学了我半天，如果以正常线段树的思维，在访问区间看一个个点是否符合要求再更新，这种想法一定是超时的。。。然后我就没有想出解法了，看了好多解法，有用数学方法求一堆复杂的式子优化的，也有线段树打tag的。。。这些我都看不懂，然后我就看了一篇树状数组做的，思路还比较简单，就是做法很巧妙，和线段树的思路差不多，以i%k的结果分组，可以分成55组进行处理，比如k=1时 分组1,2,3,4,5.。。。k=2时分组1,3,5,7.。。第二组2,4,6.。。。k=3时第一组1,4,7.。。第二组2,5,8.。第三组3,6,9.。。以此类推，一共分成55组处理（不分组会超时，我试了qaq），然后每一组就是一颗树状数组，代表着该下标的增量，每次询问时原来的值加上该坐标在每一棵含有该点的树下的增量就是询问结果，然后要解决这个问题还有一个东西要学（不学也会超时qwq），就是数组数组的成段更新，没错树状数组借助增量数组也可以实现成段更新，就是修改比如要在\[a,b\]区间增加x，那么就在a点处+x，在b+1点处-x，求某一点处a的值就是求和区间1加到a（只知道这个定理不会证明），掌握这些就可以解出这一题了，可能讲的不太清楚，发大佬博客http://www.cnblogs.com/Griselda/archive/2012/09/15/2686133.html，看完这个博客以后，才看懂另一个人的博客qaq（初学的辛酸）

我的代码是参考这个大佬写的：http://www.cnblogs.com/staginner/archive/2012/09/08/2677023.html

下面是我写的代码，里面有一些我的见解：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    int n;
    int lowbit(int x)//树状数组寻找父子区间的纽带
    {
        return x&(-x);
    }
    int tree[100][50005];
    int a[50005];
    int query(int k,int x)//这里询问某个点的值变成了从区间1加到x了，直接就是答案
    {
        int s=0;
        while(x>0)
        {
            s+=tree[k][x];
            x-=lowbit(x);
        }
        return s;
    }
    int Getv(int x)
    {
        int i;
        int s=a[x];
        for(i=1;i<=10;i++)
        {
            int t=(i-1)*10+x%i;//t为在10种k的情况下该点位置
            s+=query(t,x);
        }
        return s;
    }
    void update(int k,int x,int v)//更新还是和一般的树状数组一样
    {
        while(x<=n)
        {
            tree[k][x]+=v;
            x+=lowbit(x);
        }
    }
    void init()
    {
        int i,j;
        for(i=0;i<100;i++)//初始化
        {
            memset(tree[i],0,sizeof(tree[i][0])*(n+1));
        }
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);//保存初始值
    }
    int main()
    {
        int i,j,k,q,tag,x,y,c,d;
        while(scanf("%d",&n)!=EOF)
        {
            init();
            scanf("%d",&q);
            while(q--)
            {
                scanf("%d",&d);
                if(d==1)
                {
                    scanf("%d%d%d%d",&x,&y,&k,&c);
                    y-=(y-x)%k;//y减去区间内要更新的数字数目为不更新的数字数目
                    update((k-1)*10+x%k,x,c);//这里是树状数组的成段更新，第一个参数是值为k时，满足更新条件的区间起始位置开始往后全部加上c
                    update((k-1)*10+y%k,y+1,-c);//第一个参数是值为k时，从操作区间外的第一个开始往后减去c，就和前面的一起组成了对[x,y]的成段更新,相当于抵消的多加的c
                }
                else
                {
                    scanf("%d",&x);
                    printf("%d\n",Getv(x));
                }
            }
        }
        return 0;
    }