(BOJ)区間と2042回を求めます

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

質問する

6個の数がある.しかし、途中で頻繁に数の変更が発生し、途中である部分の和を求めたい.1,2,3,4,5という数があれば,3番目の数を6に変更し,2番目から5番目の和を求め,17を出力すればよい.そしてその状態で、5番目の数を2に変更し、3番目から5番目の数の和を求めると、12になります.

入力

第1行は数の個数N(1≦N≦1000000)とM(1≦M≦10000),K(1≦K≦10000)を与える.Mは数の変更が発生した回数であり,Kは区間の和を求める回数である.そして、2行目からN+1行目までN個の数が与えられる.そして、N+2行からN+M+K+1行に3つの整数a,b,cを与え、aが1であればb(1≦b≦N)回数をcに変更し、aが2であればb(1≦b≦N)回数からc(b≦c≦N)回数の和を求めて出力する.
入力されたすべての数字は、263-1以下の整数で-263以上です.

しゅつりょく

1行目から求めた区間の和をK行間で出力する.ただし、正解は-263以上、263-1以下の整数である.

に近づく

この問題はセグメントツリーで解決した.

セグメントツリー

セグメントツリーは、複数のデータが連続して存在する場合に、ある範囲のデータの和を求める際に使用される資料構造である.配列内の各要素はセグメントツリーのリーフノードを構成し、中間ノードはサブノードの和で構成され、ルートノードは配列内のすべてのノードの和で構成されます.
質問の入力は次のとおりです.
1
2
3
4
5
次に、配列をセグメントツリーで表します.

上記にまとめたように,本人の値は本人の左サブ項目と右サブ項目の値の加算からなる.
本人は木を作るときにノード構造体を作るのが普通ですが、この問題は完全に二進木の形で左から右に埋め尽くす形で現れるので、簡単な並びで体現すべきです.
セグメントツリーを構成するコードは次のとおりです.

long long init(int low, int high, int idx) {
	// 범위 시작점과 끝점이 같아지면 
        // 해당 인덱스(low or high)의 값을 트리 리프 노드 위치에 저장
	if (low == high) {
		tree[idx] = arr[low]; 
		return tree[idx];
	}

	// 범위의 중간 지점을 기준으로
	int mid = (low + high) / 2;
    
    	// 왼쪽 구간과 오른쪽 구간에 대해 재귀호출
        // idx는 트리 상 인덱스를 의미하며
        // 왼쪽 자식은 idx * 2, 오른쪽 자식은 idx * 2 + 1이 된다.
	tree[idx] = init(low, mid, idx * 2) + init(mid + 1, high, idx * 2 + 1);
	return tree[idx];
}

全体的に、本人の基準で規定された区間を半分に分ける場合、左区間の区間と左に置かれたサブ区間、右区間の区間と右に置かれたサブ区間.また,区間始点(low)と区間終点(high)が同じであれば,その区間の要素は1つであり,これはリーフノードであることを意味する.
この位置で値が決定された場合、その値が返され、返された値が加算され、上向きに返されます.

tree[idx] = init(low, mid, idx * 2) + init(mid + 1, high, idx * 2 + 1);

本人の左と右を再帰的に呼び出し、返された値をそれぞれの位置の値に加算します.
これで木が完成し、今から問題を解決します.解決すべき問題にはこの2つの状況がある.

と番号付けされたノードの値

を変更します.

区間bからcまでの値の和(b,cはノード番号)

1.特定番号ノードの値を変更する

aの値として1を入力する場合に実行する操作.最初のコードは次のとおりです.

void change(int b, int c, int low, int high, int idx, long long diff) {
	if (b < low || b > high) {
		return;
	}

	tree[idx] += diff;

	if (low != high) {
		int mid = (low + high) / 2;
		change(b, c, low, mid, idx * 2, diff);
		change(b, c, mid + 1, high, idx * 2 + 1, diff);
	}
}

b:値を置換するノード番号
c:変更された値(再考後、コードに不要になる可能性があります)
low:区間の開始
high:区間の末尾
diff:新しく変更した値と既存のノードの値の違い
領域内の値が変更する番号(b)に対応する場合、ノード番号を持つリーフノードに達するまで、ノード内の既存の値にdiffを追加する操作を繰り返します.
いずれにしても,あるノード(リーフノードを除く)を基準として,bが属する区間を持つノードが本人+(左サブノードまたは右サブノード)となる.したがって,このようにすれば,後で自分のノード上の子供を加算する値が自分の値となる.

方法。

上の方式は私個人から見ればそのような方式で実現されることが多いが、本人も最初はこのようにコードを書いていた.

long long change(int b, long long c, int low, int high, int idx) {
	if (b < low || b > high) {
		return tree[idx];
	}
	if (low == high && b == high) {
		tree[idx] = c;
		return tree[idx];
	}
	if (low <= b && b <= high) {
		int mid = (low + high) / 2;
		tree[idx] = change(b, c, low, mid, idx * 2) + change(b, c, mid + 1, high, idx * 2 + 1);
	}
	return tree[idx];
}

上記の方法と同様ですが、リーフノードに移動してから、親ノードの値をノードの値に対応する子ノードの値に更新し、この操作を繰り返すように構成します.
(最初にツリーを構築したときと同様)

2.区間bからcまでの値の和(b,cはノード番号)

コードは次のとおりです.

long long get(int b, int c, int low, int high, int idx) {
	// 구하고자 하는 구간이 현재 범위를 아예 벗어난 경우
	if (b > high || c < low) {
		return 0;
	}

	// 구하고자 하는 구간 내에 현재 범위가 모두 포함된 경우
	if (b <= low && high <= c) {
		return tree[idx];	
	}

	// 구하고자 하는 구간에 현재 범위가 걸쳐있는 경우
	int mid = (low + high) / 2;
	return get(b, c, low, mid, idx * 2) + get(b, c, mid + 1, high, idx * 2 + 1);
}

b:取得したい区間の開始
c:要求解の区間の端点
low:現在の領域の始点
high:現在の領域の末尾
idx:ツリー上の現在のインデックス
以下の木があると仮定して,a=3,b=9の場合の答えを解く.

円の数字はノードが持つ値(範囲に属するノードの値の和)を表し、次の数字はノード番号(範囲)を表します.
まず根から探索する.

a = 3
b = 9
low = 1
high = 9
欲しい範囲:3～9
現在の範囲:1～9
現在の範囲は求めたい範囲内であるため,サブノードを探索する.
△現在の範囲には救いたい範囲も含まれていると考えられています.
まずは、左の子から探索を開始.

(赤は現在のノード、緑は後でナビゲートするノードです.)
a = 3
b = 9
low = 1
high = 5
欲しい範囲:3～9
現在の範囲:1～5
現在の範囲は求めたい範囲内であるため,サブノードを探索する.

(赤は現在のノード、緑は後でナビゲートするノードです.)
a = 3
b = 9
low = 1
high = 3
欲しい範囲:3～9
現在の範囲:1～3
現在の範囲は求めたい範囲内であるため,サブノードを探索する.

(赤は現在のノード、緑は後でナビゲートするノードです.)
a = 3
b = 9
low = 1
high = 2
欲しい範囲:3～9
現在の範囲:1-2
現在の範囲は求めたい範囲を完全に超えているため、脱退した.

(赤は現在のノード、緑は後でナビゲートするノードです.)
a = 3
b = 9
low = 3
high = 3
欲しい範囲:3～9
現在の範囲:3
現在の範囲は求められた範囲に属している.したがって、ノードの値は正解にマージされます.

(赤は現在のノード、緑は後でナビゲートするノード、青は特定のノード)
a = 3
b = 9
low = 4
high = 5
欲しい範囲:3～9
現在の範囲:4-5
現在の範囲は求められた範囲に属している.したがって、ノードの値は正解にマージされます.

(赤は現在のノード、緑は後でナビゲートするノード、青は特定のノード)
a = 3
b = 9
low = 6
high = 9
欲しい範囲:3～9
現在の範囲:6-9
現在の範囲は求められた範囲に属している.したがって、ノードの値は正解にマージされます.

正解

3 + 9 + 30 = 42

コード#コード#

#include <iostream>

using namespace std;

const int max_num = 1e6 + 1;
long long arr[1000001];
long long tree[4000004];
int n;
int m;
int k;

long long init(int low, int high, int idx) {
	if (low == high) {
		tree[idx] = arr[low];
		return tree[idx];
	}

	int mid = (low + high) / 2;
	tree[idx] = init(low, mid, idx * 2) + init(mid + 1, high, idx * 2 + 1);
	return tree[idx];
}

void change(int b, int c, int low, int high, int idx, long long diff) {
	if (b < low || b > high) {
		return;
	}

	tree[idx] += diff;

	if (low != high) {
		int mid = (low + high) / 2;
		change(b, c, low, mid, idx * 2, diff);
		change(b, c, mid + 1, high, idx * 2 + 1, diff);
	}
}

long long get(int b, int c, int low, int high, int idx) {
	if (b > high || c < low) {
		return 0;
	}

	if (b <= low && high <= c) {
		return tree[idx];	
	}

	int mid = (low + high) / 2;
	return get(b, c, low, mid, idx * 2) + get(b, c, mid + 1, high, idx * 2 + 1);
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	init(1, n, 1);

	for (int i = 0; i < m + k; i++) {
		int a;
		int b;
		long long c;
		cin >> a >> b >> c;

		if (a == 1) {
			change(b, c, 1, n, 1, c - arr[b]);
			arr[b] = c;
		}
		else if (a == 2) {
			long long answer = get(b, c, 1, n, 1);
			cout << answer << endl;
		}
	}

	return 0;
}