[TIOJ] 1869. 堆石子遊戲

題目連結:http://tioj.infor.org/problems/1869

---

本題我一開始以為可以開個N棵線段樹之類的，結果我就TLE了QAQ，後來想想才發現N棵線段樹的話，複雜度是$O(Q N \log N)$難怪會TLE，想了想發現似乎可以樹套樹(二維BIT)，畢竟他只有區間和跟單點修改，那就直接做吧XD，複雜度$O(Q \log ^2 N)$

#include <bits/stdc++.h>
using namespace std;

#define N 1024
#define lowbit(x) (x)&(-x)

int BIT[N+10][N+10]={0};
int n;

void edit(int,int,int);
int query(int,int);

int main(){
	scanf("%d",&n);
	int type;
	while(scanf("%d",&type)!=EOF){
		if(type==1){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			x++,y++;
			edit(x,y,z);
		}else{
			int x1,y1,x2,y2;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			x1++,y1++,x2++,y2++;
			int s = query(x2,y2) + query(x1-1,y1-1) - query(x1-1,y2) - query(x2,y1-1);
			printf("%d\n",s);
		}
	}
	return 0;
}

void edit(int x,int y,int v){
	while(x<=n){
		int yy=y;
		while(yy<=n){
			BIT[x][yy]+=v;
			yy+=lowbit(yy);
		}
		x+=lowbit(x);
	}
}

int query(int x,int y){
	int sum=0;
	while(x>0){
		int yy=y;
		while(yy>0){
			sum+=BIT[x][yy];
			yy-=lowbit(yy);
		}
		x-=lowbit(x);
	}
	return sum;
}