백준11658 구간 합 구하기3

작성일 | In

문제 링크

  • http://icpc.me/11658

사용 알고리즘

  • 2D Segment Tree

시간복잡도

  • 쿼리 당 O(lg2N)

풀이

신나게 2D세그를 짜서 명쾌하게 정답을 띄웁시다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
using namespace std;

struct Seg {
	int tree[3030];
	int bias;
	void init(int n) { for (bias = 1; bias < n; bias <<= 1); }
	void update(int x, int v) {
		x += bias; tree[x] = v;
		while (x >>= 1) {
			tree[x] = tree[x << 1] + tree[x << 1 | 1];
		}
	}
	int query(int l, int r) {
		l += bias, r += bias;
		int ret = 0;
		while (l < r) {
			if (l & 1) ret += tree[l++];
			if (!(r & 1)) ret += tree[r--];
			l >>= 1, r >>= 1;
		}
		if (l == r) ret += tree[r];
		return ret;
	}
};

struct Seg2d {
	Seg tree[3030];
	int bias;
	void init(int n, int m) {
		for (bias = 1; bias < n; bias <<= 1);
		for (int i = 0; i <= bias * 2; i++) tree[i].init(m);
	}
	void update(int x, int y, int v) {
		x += bias; tree[x].update(y, v);
		while (x >>= 1) {
			int t1 = tree[x << 1].query(y, y);
			int t2 = tree[x << 1 | 1].query(y, y);
			tree[x].update(y, t1 + t2);
		}
	}
	int query(int l, int r, int ll, int rr) {
		l += bias, r += bias;
		int ret = 0;
		while (l < r) {
			if (l & 1) ret += tree[l++].query(ll, rr);
			if (!(r & 1)) ret += tree[r--].query(ll, rr);
			l >>= 1, r >>= 1;
		}
		if (l == r) ret += tree[r].query(ll, rr);
		return ret;
	}
}seg;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	seg.init(n, n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int t; cin >> t;
			seg.update(i, j, t);
		}
	}

	while (m--) {
		int op, a, b, c, d; cin >> op;
		if (!op) {
			cin >> a >> b >> c;
			seg.update(a, b, c);
		}
		else {
			cin >> a >> c >> b >> d;
			cout << seg.query(a, b, c, d) << "\n";
		}
	}
}