Ежедневный бит (е) C ++ # 191, Общая задача на собеседовании: сумма областей O (1).

Сегодня мы рассмотрим распространенную задачу интервью C++: O(1) сумма областей.

Учитывая сетку целых чисел, предоставьте метод, который вычисляет сумму субрегиона:

  • int64_t Grid::region_sum(Координата сверху_слева, Координата снизу_справа) const;

Метод должен работать в O(1); однако вам разрешена предварительная обработка и O(|grid|) дополнительная память.

Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/nxvqrqfWq.

Решение

Во-первых, давайте рассмотрим более простую задачу только с одним измерением. Как мы можем вернуть сумму смежных элементов в одномерном массиве за O(1)?

Например, если задан массив {5,2,3,0,1,4}, допустим, мы хотим вычислить сумму элементов по индексам {3..5}. Мы знаем, что Sum({3..5}) совпадает с Sum({0..5})-Sum({0..2}). Поскольку нам разрешена предварительная обработка, мы можем вычислить все суммы префиксов, что позволит нам вернуть любую сумму за O(1).

Распространить эту идею на 2D несложно; нам нужно только быть осторожным с перекрывающимися областями и правильно с ними обращаться.

Если мы будем следовать подходу из 1D-версии, мы получим предварительно вычисленные суммы для каждой координаты, где сумма представляет собой площадь {0, 0}..{row, col}. Затем мы можем вычислить сумму синей области, вычитая две перекрывающиеся красно-зеленые области и добавляя зеленую область.

struct Coord {
    int64_t row;
    int64_t col;
};

struct Grid {
    Grid(const std::vector<std::vector<int64_t>>& matrix) 
        : sums(matrix.size(), 
               std::vector<int64_t>(matrix[0].size(),0)) {
        for (int64_t i = 0; i < std::ssize(matrix); ++i)
        for (int64_t j = 0; j < std::ssize(matrix[i]); ++j) {
            // digit on this coordinate
            sums[i][j] += matrix[i][j]; 
            // sum on this column, upto the previous row
            if (i > 0)
                sums[i][j] += sums[i-1][j];
            // sum on this row, upto the previous column
            if (j > 0)
                sums[i][j] += sums[i][j-1]; 
            // we are doublecounting the shared area between the sums
            if (i > 0 && j > 0)
                sums[i][j] -= sums[i-1][j-1];
        }
    }
    
    int64_t region_sum(Coord top_left, Coord bottom_right) const {
        // sum upto the bottom right coordinate
        int64_t result = sums[bottom_right.row][bottom_right.col];
        // minus the rectangle between 
        // the left column and start of the grid
        if (top_left.col > 0)
            result -= sums[bottom_right.row][top_left.col-1];
        // minus the rectangle between 
        // the top row and start of the grid
        if (top_left.row > 0)
            result -= sums[top_left.row-1][bottom_right.col];
        // we have removed the rectangle that sits diagonaly 
        // from this area twice, need to add it back
        if (top_left.col > 0 && top_left.row > 0)
            result += sums[top_left.row-1][top_left.col-1];
        return result;
    }
private:
    std::vector<std::vector<int64_t>> sums;
};

Откройте решение в Compiler Explorer.