【題解】Zerojudge a693 - 吞食天地

題目連結

題目大意

給定一個長度為 $n$ 數列 $a$ 和 $q$ 筆查詢，每次查詢數列中一個區間的加總。

• $1 \leq n, m \leq 10^5$

題解

求一個區間的加總可以運用前綴和的技巧先透過 $O(n) 預處理後 $O(1)$ 查詢。定義 $S_k = \sum_{i = 0}^k a_i$，則要求 $a_l + \dots + a_r$ 等價於 $S_r - S_{l - 1}$。最後需要注意本題輸入是讀到 EOF 結束。其他實作的細節請參考 code。

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	while(cin >> n >> q) {
		vector<long long> pref(n + 1);
		for(int i = 0; i < n; i++) {
			long long x;
			cin >> x;
			pref[i + 1] = pref[i] + x;
		}
		while(q--) {
			int l, r;
			cin >> l >> r;
			l--;
			cout << pref[r] - pref[l] << "\n";
		}
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge a693 - 吞食天地