Префиксные суммы

Материал из Олимпиадное программирование в УлГТУ
Версия от 17:27, 13 марта 2023; Ctrlalt (обсуждение | вклад) (Новая страница: «== Одномерный случай == {| width="100%" | width=50% | long long getSum(vector<long long> &p, int l, int r) { return p[r] - (l ? p[l - 1] :...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Одномерный случай

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;
    }
};

Ссылки

Теория: