Ежедневный бит (е) 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.