学步园

HDU_4267

    根据k的值建立10类树状数组，每类中根据i%k的不同建立k棵树状数组，也就是55棵树状数组，这样每次修改操作只对其中1棵树状数组进行操作，所以是O(logN)的复杂度，每次查询只对其中10棵树状数组统计增量和，所以是O(10*logN)的复杂度。

#include<stdio.h>
#include<string.h>
#define MAXD 50010
int N, M, d[100][MAXD], a[MAXD];
void insert(int k, int x, int v)
{
    for(; x <= N; x += x & -x) d[k][x] += v;
}
void init()
{
    int i, j;
    for(i = 1; i <= N; i ++) scanf("%d", &a[i]);
    for(i = 0; i < 100; i ++) memset(d[i], 0, sizeof(d[i][0]) * (N + 1));
}
int query(int id)
{
    int i, k, x, ans = 0;
    for(i = 1; i <= 10; i ++)
    {
        k = (i - 1) * 10 + id % i;
        for(x = id; x > 0; x -= x & -x) ans += d[k][x];
    }
    return a[id] + ans;
}
void solve()
{
    int i, op, a, b, k, c;
    scanf("%d", &M);
    for(i = 0; i < M; i ++)
    {
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d%d%d%d", &a, &b, &k, &c);
            b -= (b - a) % k;
            insert(10 * (k - 1) + a % k, a, c);
            if(b < N) insert(10 * (k - 1) + b % k, b + 1, -c);
        }
        else if(op == 2)
        {
            scanf("%d", &a);
            printf("%d\n", query(a));
        }
    }
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        init();
        solve();
    }
    return 0;
}