https://www.acmicpc.net/problem/2268

 

2268번: 수들의 합

첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를 ��

www.acmicpc.net

문제

N개의 수 A[1], A[2], …, A[N] 이 주어졌을 때, 함수 Sum(i, j)는 A[i]+A[i+1]+…+A[j]를 구하는 함수이다. (i>j일 경우에는 A[j]+A[j+1]+...+A[i]) A가 주어졌을 때, Sum(i, j)를 구하는 것은 매우 쉬운 문제이다. 이러한 (i, j)가 여러 개 주어졌을 때도 별로 어려운 문제는 아니다.

Sum함수와 더불어 Modify라는 함수를 정의하자. Modify(i, k)를 수행하면 A[i]=k가 되는 함수이다. Sum함수와 Modify 함수의 사용 목록이 주어졌을 때, 이에 해당하는 연산을 하는 프로그램을 작성하시오. 두 함수를 섞어서 사용할 수도 있다.

입력
첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를 나타내며, 0일 경우에는 Sum 함수를, 1일 경우에는 Modify 함수를 나타낸다. 다음 두 수는 각 함수의 인자 (i, j)나 (i, k)를 나타낸다. 처음에는 A[1]=A[2]=…A[N]=0이다. Modify인 경우에 1 ≤ k ≤ 100,000 이다.

출력
Sum 함수의 개수만큼 각 줄에 Sum 함수의 리턴값을 출력한다.

예제 입력 1 
3 5
0 1 3
1 1 2
1 2 3
0 2 3
0 1 3
예제 출력 1 
0
3
5
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long ll;
int N, M;
vector <ll> nums;

struct IndexedTree {
	vector <ll> tree;
	vector <ll> num;
	int leafSize = 0, depth = 0;

	IndexedTree(vector <ll> num1) {
		num = num1;
		while (pow(2, depth) < num1.size()) {
			depth++;
		}
		leafSize = pow(2, depth);
		tree.resize(2 * leafSize);
	}

	void update(int node, int left, int right, int index, int diff) {
		if (index < left || right < index) {
			return;
		}
		else {
			tree[node] += diff;
			if (left != right) {
				ll mid = (left + right) / 2;
				update(node * 2, left, mid, index, diff);
				update(node * 2 + 1, mid + 1, right, index, diff);
			}
		}
	}

	ll query(int node, int left, int right, int qLeft, int qRight) {
		if (right < qLeft || qRight < left) {
			return 0;
		}
		else if (qLeft <= left && right <= qRight) {
			return tree[node];
		}
		else {
			ll mid = (left + right) / 2;
			return query(node * 2, left, mid, qLeft, qRight) + query(node * 2 + 1, mid + 1, right, qLeft, qRight);
		}
	}
};


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	freopen("input.txt", "r", stdin);

	cin >> N >> M;
	nums.resize(N + 1);
	IndexedTree h(nums);
	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			int temp = nums[b];
			int update = c - temp;
			nums[b] = c;
			h.update(1, 1, h.leafSize, b, update);
		}
		else if(a==0) {
			if (c < b) {
				swap(b, c);
			}
			cout << h.query(1, 1, h.leafSize, b, c) <<"\n";
		}
	}

	return 0;
}

+ Recent posts