고전 알고리즘 | 2 차원 트 리 배열

2 차원 배열 을 지정 하고 두 가지 조작 을 지정 합 니 다. 첫 번 째 는 s x1 y1 x2 y2 를 입력 하 십시오. 2 차원 배열 에서 (x1, y1) 부터 (x2, y2) 까지 의 사각형 의 모든 수의 합 을 조회 하 는 것 을 의미 합 니 다. 두 번 째 조 는 a x1 y1 value 로 배열 에서 num [x1] [y1] 의 수 를 value 로 추가 하 는 것 을 의미 합 니 다. 어떻게 가장 빠 른 시간 안에 결 과 를 얻 을 수 있 습 니까?
2 차원 트 리 배열 을 사용 할 수 있 습 니 다.
먼저 lowBit (n) 입 니 다. 이 함수 의 기능 은 n 의 가장 낮은 1 이 대표 하 는 수의 크기 를 되 돌려 주 는 것 입 니 다. 예 를 들 어 5, 2 진법 이 101 이면 가장 낮은 1 은 1 입 니 다. 2 진법 101000 에 있어 가장 낮은 1 은 1000 이 고 lowBit 는 두 가지 실현 방식 이 있 습 니 다. 하 나 는 n – (n & (n – 1) 이 고 두 번 째 는 n & (n) 이 며 두 번 째 는 n & (n) 입 니 다. 두 번 째 로 이용 하 는 패 치 의 성질 입 니 다.이 두 가지 방식 의 결 과 는 사실 같다.
여기에 보조 배열 tree 를 사용 합 니 다.list，tree_list [n] 은 treelist[n] + tree_list[n-1]+。。。tree_list [n – lowBit (n)], 1 차원 상황 입 니 다. 2 차원 treelist 는 2 차원 이 고 원 리 는 같다.
num [x] 를 수정 할 때, 모든 n > x, n – lowBit (n) < x 의 n, 그 treelist [n] 은 모두 수정 이 필요 합 니 다. for (int i = x, i < = size (), i + = lowBit (i) 를 사용 하면 size () 보다 작은 요 구 를 만족 시 키 는 n 을 찾 을 수 있 습 니 다. 이것 은 1 차원 처리 이 고 2 차원 처리 방식 은 같 습 니 다.
여 기 는 x 대표 줄 수, y 대표 열 수 를 주의해 야 합 니 다. 줄 이 옮 겨 다 니 거나 열 이 옮 겨 다 닐 때 for 순환 조건 에 주의해 야 합 니 다. 또한 숫자 세그먼트 를 조회 할 때 1 을 줄 이 는 문 제 를 주의해 야 합 니 다.

#include
using namespace std; 

int tree_list[1001][1001] = { 0 };

int lowBit(int x)
{
	return x & (-x);
}
int search(int x, int y)
{
	int result = 0;
	for (int i = x; i > 0; i -= lowBit(i))
		for (int j = y; j > 0; j -= lowBit(j))
			result += tree_list[i][j];
	return result;
}

void add(int x, int y, int value, int w,int h)
{
	for (int i = x; i <= h; i += lowBit(i))
		for (int j = y; j <= w; j += lowBit(j))
			tree_list[i][j] += value;
}

int main()
{
	int num[][6] = {
	{0, 0, 0, 0, 0, 0},
	{0, 1, 2, 3, 4, 5},
	{0, 6, 7, 8, 1, 1},
	{0, 6, 7, 8, 1, 1 },
	{0, 1, 1, 1, 1, 1 }
	};
	int h = 4;
	int w = 5;//           1   
	for(int i=1;i<=h;i++)
		for (int j = 1; j <= w; j++)
		{
			add(i, j, num[i][j], w, h);
		}
	char j_type = 'a';
	int x, y, v;
	int x2, y2;
	while (cin >> j_type)
	{
		if (j_type == 'a')
		{
			cin >> x >> y >> v;
			add(x, y, v, w, h);
		}
		else
		{
			cin >> x >> y >> x2 >> y2;
			int A1, A2, A3, A4;
			A1 = search(x-1, y-1);
			A2 = search(x2, y2);
			A3 = search(x-1, y2);
			A4 = search(x2, y-1);
			cout << A2 - A3 - A4 + A1 << endl;
		}
	}
	return 0;
}