https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B5_%D1%81%D1%83%D0%BC%D0%BC%D1%8B
Префиксные суммы - История изменений
2026-05-13T12:11:58Z
История изменений этой страницы в вики
MediaWiki 1.39.3
https://acm.khpnets.info/w39/index.php?title=%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B5_%D1%81%D1%83%D0%BC%D0%BC%D1%8B&diff=2854&oldid=prev
Ctrlalt: Новая страница: «== Одномерный случай == {| width="100%" | width=50% | long long getSum(vector<long long> &p, int l, int r) { return p[r] - (l ? p[l - 1] :...»
2023-03-13T17:27:06Z
<p>Новая страница: «== Одномерный случай == {| width="100%" | width=50% | long long getSum(vector<long long> &p, int l, int r) { return p[r] - (l ? p[l - 1] :...»</p>
<p><b>Новая страница</b></p><div>== Одномерный случай ==<br />
<br />
{| width="100%"<br />
| width=50% |<br />
<br />
long long getSum(vector<long long> &p, int l, int r) {<br />
return p[r] - (l ? p[l - 1] : 0);<br />
}<br />
<br />
int main() {<br />
int size, queryCount;<br />
cin >> size >> queryCount;<br />
<br />
vector<long long> p(size);<br />
for (int i = 0; i < size; i++) {<br />
cin >> p[i];<br />
if (i)<br />
p[i] += p[i - 1];<br />
}<br />
<br />
for (int i = 0; i < queryCount; i++) {<br />
int l, r;<br />
cin >> l >> r;<br />
cout << getSum(p, l, r) << "\n";<br />
}<br />
}<br />
<br />
| width="10px" | &nbsp;<br />
| width=50% |<br />
<br />
struct PrefixSum {<br />
vector<long long> p;<br />
<br />
PrefixSum(vector<long long> &a) {<br />
p = a;<br />
partial_sum(p.begin(), p.end(), p.begin());<br />
}<br />
<br />
long long getSum(int l, int r) {<br />
return p[r] - (l ? p[l - 1] : 0);<br />
}<br />
};<br />
<br />
|}<br />
<br />
== Двумерный случай ==<br />
<br />
{| width="100%"<br />
| width=50% |<br />
<br />
long long getSum(vector<vector<long long>> &p, int yl, int xl, int yr, int xr) {<br />
long long res = p[yr][xr];<br />
if (yl)<br />
res -= p[yl - 1][xr];<br />
if (xl)<br />
res -= p[yr][xl - 1];<br />
if (yl && xl)<br />
res += p[yl - 1][xl - 1];<br />
return res;<br />
}<br />
<br />
int main() {<br />
int h, w, queryCount;<br />
cin >> h >> w >> queryCount;<br />
<br />
vector<vector<long long>> p(h, vector<long long>(w));<br />
for (int y = 0; y < h; y++) {<br />
for (int x = 0; x < w; x++) {<br />
cin >> p[y][x];<br />
if (y)<br />
p[y][x] += p[y - 1][x];<br />
if (x)<br />
p[y][x] += p[y][x - 1];<br />
if (y && x)<br />
p[y][x] -= p[y - 1][x - 1];<br />
}<br />
}<br />
<br />
for (int i = 0; i < queryCount; i++) {<br />
int yl, xl, yr, xr;<br />
cin >> yl >> xl >> yr >> xr;<br />
cout << getSum(p, yl, xl, yr, xr) << "\n";<br />
}<br />
}<br />
<br />
| width="10px" | &nbsp;<br />
| width=50% |<br />
<br />
struct PrefixSum2D {<br />
vector<vector<long long>> p;<br />
<br />
PrefixSum2D(vector<vector<long long>> &a) {<br />
p = a;<br />
for (int y = 0; y < p.size(); y++) {<br />
for (int x = 0; x < p[0].size(); x++) {<br />
if (y)<br />
p[y][x] += p[y - 1][x];<br />
if (x)<br />
p[y][x] += p[y][x - 1];<br />
if (y && x)<br />
p[y][x] -= p[y - 1][x - 1];<br />
}<br />
}<br />
}<br />
<br />
long long getSum(int yl, int xl, int yr, int xr) {<br />
long long res = p[yr][xr];<br />
if (yl)<br />
res -= p[yl - 1][xr];<br />
if (xl)<br />
res -= p[yr][xl - 1];<br />
if (yl && xl)<br />
res += p[yl - 1][xl - 1];<br />
return res;<br />
}<br />
};<br />
<br />
|}<br />
<br />
== Ссылки ==<br />
<br />
Теория:<br />
* [https://brestprog.by/topics/prefixsums/ brestprog.by — Префиксные суммы]<br />
* [https://notes.algoprog.ru/ru/shortideas/03_x_prefix_sums.html notes.algoprog.ru — Префиксные суммы и смежные темы]<br />
* usaco.guide — [https://usaco.guide/silver/prefix-sums?lang=cpp Introduction to Prefix Sums], [https://usaco.guide/silver/more-prefix-sums?lang=cpp More on Prefix Sums]<br />
* [https://www.youtube.com/watch?v=5iW84xlL0j0 youtube.com — Префиксные суммы (Е. Горбачев)]<br />
<br />
[[Category:Структуры данных для задач RSQ/RMQ]]</div>
Ctrlalt