Префиксные суммы
Перейти к навигации
Перейти к поиску
Одномерный случай
long long getSum(vector<long long> &p, int l, int r) {
return p[r] - (l ? p[l - 1] : 0);
}
int main() {
int size, queryCount;
cin >> size >> queryCount;
vector<long long> p(size);
for (int i = 0; i < size; i++) {
cin >> p[i];
if (i)
p[i] += p[i - 1];
}
for (int i = 0; i < queryCount; i++) {
int l, r;
cin >> l >> r;
cout << getSum(p, l, r) << "\n";
}
}
|
struct PrefixSum {
vector<long long> p;
PrefixSum(vector<long long> &a) {
p = a;
partial_sum(p.begin(), p.end(), p.begin());
}
long long getSum(int l, int r) {
return p[r] - (l ? p[l - 1] : 0);
}
};
|
Двумерный случай
long long getSum(vector<vector<long long>> &p, int yl, int xl, int yr, int xr) {
long long res = p[yr][xr];
if (yl)
res -= p[yl - 1][xr];
if (xl)
res -= p[yr][xl - 1];
if (yl && xl)
res += p[yl - 1][xl - 1];
return res;
}
int main() {
int h, w, queryCount;
cin >> h >> w >> queryCount;
vector<vector<long long>> p(h, vector<long long>(w));
for (int y = 0; y < h; y++) {
for (int x = 0; x < w; x++) {
cin >> p[y][x];
if (y)
p[y][x] += p[y - 1][x];
if (x)
p[y][x] += p[y][x - 1];
if (y && x)
p[y][x] -= p[y - 1][x - 1];
}
}
for (int i = 0; i < queryCount; i++) {
int yl, xl, yr, xr;
cin >> yl >> xl >> yr >> xr;
cout << getSum(p, yl, xl, yr, xr) << "\n";
}
}
|
struct PrefixSum2D {
vector<vector<long long>> p;
PrefixSum2D(vector<vector<long long>> &a) {
p = a;
for (int y = 0; y < p.size(); y++) {
for (int x = 0; x < p[0].size(); x++) {
if (y)
p[y][x] += p[y - 1][x];
if (x)
p[y][x] += p[y][x - 1];
if (y && x)
p[y][x] -= p[y - 1][x - 1];
}
}
}
long long getSum(int yl, int xl, int yr, int xr) {
long long res = p[yr][xr];
if (yl)
res -= p[yl - 1][xr];
if (xl)
res -= p[yr][xl - 1];
if (yl && xl)
res += p[yl - 1][xl - 1];
return res;
}
};
|
Ссылки
Теория: