HDU_4267
根据k的值建立10类树状数组，每类中根据i%k的不同建立k棵树状数组，也就是55棵树状数组，这样每次修改操作只对其中1棵树状数组进行操作，所以是O(logN)的复杂度，每次查询只对其中10棵树状数组统计增量和，所以是O(10*logN)的复杂度。
#include#include #define MAXD 50010int 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;}