Рубрики

Submatrix Sum Queries

Учитывая матрицу размера M x N, существует большое количество запросов для поиска сумм подматриц. Входными данными для запросов являются левый верхний и правый нижний индексы подматрицы, чью сумму нужно выяснить.

Как предварительно обработать матрицу так, чтобы запросы суммы подматрицы могли быть выполнены за O (1) время.

Пример :

tli :  Row number of top left of query submatrix
tlj :  Column number of top left of query submatrix
rbi :  Row number of bottom right of query submatrix
rbj :  Column number of bottom right of query submatrix

Input: mat[M][N] = {{1, 2, 3, 4, 6},
                    {5, 3, 8, 1, 2},
                    {4, 6, 7, 5, 5},
                    {2, 4, 8, 9, 4} };
Query1: tli = 0, tlj = 0, rbi = 1, rbj = 1
Query2: tli = 2, tlj = 2, rbi = 3, rbj = 4
Query3: tli = 1, tlj = 2, rbi = 3, rbj = 3;

Output:
Query1: 11  // Sum between (0, 0) and (1, 1)
Query2: 38  // Sum between (2, 2) and (3, 4)
Query3: 38  // Sum between (1, 2) and (3, 3)

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Идея состоит в том, чтобы сначала создать вспомогательную матрицу aux [M] [N] так , чтобы aux [i] [j] сохраняла сумму элементов в подматрице от (0,0) до (i, j). Как только aux [] [] построен, мы можем вычислить сумму подматрицы между (tli, tlj) и (rbi, rbj) за O (1) времени. Нам нужно рассмотреть aux [rbi] [rbj] и вычесть все ненужные элементы. Ниже приведено полное выражение для вычисления суммы подматрицы за время O (1).

Sum between (tli, tlj) and (rbi, rbj) is,
   aux[rbi][rbj] - aux[tli-1][rbj] - 
   aux[rbi][tlj-1] + aux[tli-1][tlj-1]

The submatrix aux[tli-1][tlj-1] is added because  
elements of it are subtracted twice.

Иллюстрация:

mat[M][N] = {{1, 2, 3, 4, 6},
             {5, 3, 8, 1, 2},
             {4, 6, 7, 5, 5},
             {2, 4, 8, 9, 4} };

We first preprocess the matrix and build
following aux[M][N]
aux[M][N] = {1,  3,   6,  10, 16}
            {6,  11,  22, 27,  35},
            {10, 21,  39, 49,  62},  
            {12, 27,  53, 72,  89} }

Query : tli = 2, tlj = 2, rbi = 3, rbj = 4  
      
Sum between (2, 2) and (3, 4) = 89 - 35 - 27 + 11
                              = 38
         

Как построить aux [M] [N]?
1. Скопируйте первую строку мата [] [] в aux [] []
2. Составьте столбцовую сумму матрицы и сохраните ее.
3. Выполните строчную сумму обновленной матрицы aux [] [] в шаге 2.

Ниже приведена программа, основанная на представленной выше идее.

C ++

// C ++ программа для вычисления суммы запроса подматрицы в O (1)
// время
#include<iostream>

using namespace std;

#define M 4
#define N 5

  
// Функция предварительной обработки ввода mat [M] [N]. Эта функция
// в основном заполняет aux [M] [N] так, что aux [i] [j] хранит сумму
// элементов от (0,0) до (i, j)

int preProcess(int mat[M][N], int aux[M][N])

{

   // Копируем первую строку mat [] [] в aux [] []

   for (int i=0; i<N; i++)

      aux[0][i] = mat[0][i];

  

   // Делаем столбцы мудрой суммы

   for (int i=1; i<M; i++)

      for (int j=0; j<N; j++)

         aux[i][j] = mat[i][j] + aux[i-1][j];

  

   // Сделать строку мудрой суммы

   for (int i=0; i<M; i++)

      for (int j=1; j<N; j++)

         aux[i][j] += aux[i][j-1];

}

  
// AO (1) функция времени для вычисления суммы подматрицы
// между (tli, tlj) и (rbi, rbj), используя aux [] []
// который построен функцией preprocess

int sumQuery(int aux[M][N], int tli, int tlj, int rbi,

                                              int rbj)

{

    // результат теперь является суммой элементов между (0, 0) и

    // (rbi, rbj)

    int res = aux[rbi][rbj];

  

    // Удалить элементы между (0, 0) и (tli-1, rbj)

    if (tli > 0)

       res = res - aux[tli-1][rbj];

  

    // Удалить элементы между (0, 0) и (rbi, tlj-1)

    if (tlj > 0)

       res = res - aux[rbi][tlj-1];

  

    // Добавить aux [tli-1] [tlj-1] как элементы между (0, 0)

    // и (tli-1, tlj-1) вычитаются дважды

    if (tli > 0 && tlj > 0)

       res = res + aux[tli-1][tlj-1];

  

    return res;

}

  
// Драйвер программы

int main()

{

   int mat[M][N] = {{1, 2, 3, 4, 6},

                    {5, 3, 8, 1, 2},

                    {4, 6, 7, 5, 5},

                    {2, 4, 8, 9, 4} };

   int aux[M][N];

  

   preProcess(mat, aux);

  

   int tli = 2, tlj = 2, rbi = 3, rbj = 4;

   cout << "\nQuery1: " << sumQuery(aux, tli, tlj, rbi, rbj);

  

   tli = 0, tlj = 0, rbi = 1, rbj = 1;

   cout << "\nQuery2: " << sumQuery(aux, tli, tlj, rbi, rbj);

  

   tli = 1, tlj = 2, rbi = 3, rbj = 3;

   cout << "\nQuery3: " << sumQuery(aux, tli, tlj, rbi, rbj);

  

   return 0;

}

Джава

// Java-программа для вычисления запроса подматрицы
// сумма за O (1) раз

class GFG {

      

    static final int M = 4;

    static final int N = 5;

      

    // Функция предварительной обработки ввода mat [M] [N].

    // Эта функция в основном заполняет aux [M] [N]

    // такой, что aux [i] [j] хранит сумму

    // элементы от (0,0) до (i, j)

    static int preProcess(int mat[][], int aux[][])

    {

          

        // Копируем первую строку mat [] [] в aux [] []

        for (int i = 0; i < N; i++)

            aux[0][i] = mat[0][i];

          

        // Делаем столбцы мудрой суммы

        for (int i = 1; i < M; i++)

            for (int j = 0; j < N; j++)

                aux[i][j] = mat[i][j] + 

                                aux[i-1][j];

          

        // Сделать строку мудрой суммы

        for (int i = 0; i < M; i++)

            for (int j = 1; j < N; j++)

                aux[i][j] += aux[i][j-1];

                  

        return 0;

    }

      

    // AO (1) функция времени для вычисления суммы

    // подматрицы между (tli, tlj) и

    // (rbi, rbj) используя aux [] [], который

    // построено функцией препроцессора

    static int sumQuery(int aux[][], int tli, 

                    int tlj, int rbi, int rbj)

    {

          

        // результат теперь сумма элементов

        // между (0, 0) и (rbi, rbj)

        int res = aux[rbi][rbj];

      

        // Удалить элементы между (0, 0)

        // и (tli-1, rbj)

        if (tli > 0)

            res = res - aux[tli-1][rbj];

      

        // Удалить элементы между (0, 0)

        // и (rbi, tlj-1)

        if (tlj > 0)

            res = res - aux[rbi][tlj-1];

      

        // Добавить aux [tli-1] [tlj-1] в качестве элементов

        // между (0, 0) и (tli-1, tlj-1)

        // вычитаем дважды

        if (tli > 0 && tlj > 0)

            res = res + aux[tli-1][tlj-1];

      

        return res;

    }

      

    // Код драйвера

    public static void main (String[] args)

    {

        int mat[][] = {{1, 2, 3, 4, 6},

                       {5, 3, 8, 1, 2},

                       {4, 6, 7, 5, 5},

                       {2, 4, 8, 9, 4}};

                         

        int aux[][] = new int[M][N];

          

        preProcess(mat, aux);

          

        int tli = 2, tlj = 2, rbi = 3, rbj = 4;

        System.out.print("\nQuery1: "

            + sumQuery(aux, tli, tlj, rbi, rbj));

          

        tli = 0; tlj = 0; rbi = 1; rbj = 1;

        System.out.print("\nQuery2: "

            + sumQuery(aux, tli, tlj, rbi, rbj));

          

        tli = 1; tlj = 2; rbi = 3; rbj = 3;

        System.out.print("\nQuery3: " 

            + sumQuery(aux, tli, tlj, rbi, rbj));

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python 3 программа для вычисления подматрицы
# сумма запроса за O (1) раз

  

M = 4

N = 5

  
# Функция предварительной обработки входного мата [M] [N].
# Эта функция в основном заполняет вспомогательные [M] [N]
# такое, что aux [i] [j] хранит сумму
Количество элементов от (0,0) до (i, j)

def preProcess(mat, aux):

      

    # Скопировать первый ряд мата [] [] в aux [] []

    for i in range(0, N, 1):

        aux[0][i] = mat[0][i]

  

    # Делать столбец мудрой суммы

    for i in range(1, M, 1):

        for j in range(0, N, 1):

            aux[i][j] = mat[i][j] + aux[i - 1][j]

  

    # Есть ли в строке мудрая сумма

    for i in range(0, M, 1):

        for j in range(1, N, 1):

            aux[i][j] += aux[i][j - 1]

  
# AO (1) функция времени для вычисления суммы подматрицы
# между (tli, tlj) и (rbi, rbj) с помощью aux [] []
# который построен функцией preprocess

def sumQuery(aux, tli, tlj, rbi, rbj):

      

    # результат теперь является суммой элементов

    # между (0, 0) и (rbi, rbj)

    res = aux[rbi][rbj]

  

    # Удалить элементы между (0, 0)

    # и (tli-1, rbj)

    if (tli > 0):

        res = res - aux[tli - 1][rbj]

  

    # Удалить элементы между (0, 0)

    # и (rbi, tlj-1)

    if (tlj > 0):

        res = res - aux[rbi][tlj - 1]

  

    # Добавить aux [tli-1] [tlj-1] в качестве элементов

    # между (0, 0) и (tli-1, tlj-1)

    # вычитаются дважды

    if (tli > 0 and tlj > 0):

        res = res + aux[tli - 1][tlj - 1]

  

    return res

  
Код водителя

if __name__ == '__main__':

    mat = [[1, 2, 3, 4, 6],

           [5, 3, 8, 1, 2],

           [4, 6, 7, 5, 5],

           [2, 4, 8, 9, 4]]

aux = [[0 for i in range(N)] 

          for j in range(M)]

  
preProcess(mat, aux)

  

tli = 2

tlj = 2

rbi = 3

rbj = 4

print("Query1:", sumQuery(aux, tli, tlj, rbi, rbj))

  

tli = 0

tlj = 0

rbi = 1

rbj = 1

print("Query2:", sumQuery(aux, tli, tlj, rbi, rbj))

  

tli = 1

tlj = 2

rbi = 3

rbj = 3

print("Query3:", sumQuery(aux, tli, tlj, rbi, rbj))

  
# Этот код предоставлен
# Shashank_Sharma

C #

// C # программа для вычисления подматрицы
// сумма запроса за O (1) раз

using System;

  

class GFG

    static int M = 4;

    static int N = 5;

      

    // Функция предварительной обработки ввода mat [M] [N].

    // Эта функция в основном заполняет aux [M] [N]

    // такой, что aux [i] [j] хранит сумму

    // элементы от (0,0) до (i, j)

    static int preProcess(int [,]mat, int [,]aux)

    {

        // Копируем первую строку mat [] [] в aux [] []

        for (int i = 0; i < N; i++)

            aux[0,i] = mat[0,i];

          

        // Делаем столбцы мудрой суммы

        for (int i = 1; i < M; i++)

            for (int j = 0; j < N; j++)

                aux[i,j] = mat[i,j] + aux[i-1,j];

          

        // Сделать строку мудрой суммы

        for (int i = 0; i < M; i++)

            for (int j = 1; j < N; j++)

                aux[i,j] += aux[i,j-1];

                  

        return 0;

    }

      

    // AO (1) функция времени для вычисления суммы

    // подматрицы между (tli, tlj) и

    // (rbi, rbj) используя aux [] [], который

    // построено функцией препроцессора

    static int sumQuery(int [,]aux, int tli, 

                        int tlj, int rbi, int rbj)

    {

        // результат теперь сумма элементов

        // между (0, 0) и (rbi, rbj)

        int res = aux[rbi,rbj];

      

        // Удалить элементы между (0, 0)

        // и (tli-1, rbj)

        if (tli > 0)

            res = res - aux[tli-1,rbj];

      

        // Удалить элементы между (0, 0)

        // и (rbi, tlj-1)

        if (tlj > 0)

            res = res - aux[rbi,tlj-1];

      

        // Добавить aux [tli-1] [tlj-1] в качестве элементов

        // между (0, 0) и (tli-1, tlj-1)

        // вычитаем дважды

        if (tli > 0 && tlj > 0)

            res = res + aux[tli-1,tlj-1];

      

        return res;

    }

      

    // Код драйвера

    public static void Main ()

    {

        int [,]mat = {{1, 2, 3, 4, 6},

                      {5, 3, 8, 1, 2},

                      {4, 6, 7, 5, 5},

                      {2, 4, 8, 9, 4}};

                          

        int [,]aux = new int[M,N];

          

        preProcess(mat, aux);

          

        int tli = 2, tlj = 2, rbi = 3, rbj = 4;

          

        Console.Write("\nQuery1: "

                      sumQuery(aux, tli, tlj, rbi, rbj));

          

        tli = 0; tlj = 0; rbi = 1; rbj = 1;

          

        Console.Write("\nQuery2: " +

                      sumQuery(aux, tli, tlj, rbi, rbj));

          

        tli = 1; tlj = 2; rbi = 3; rbj = 3;

          

        Console.Write("\nQuery3: "

                      sumQuery(aux, tli, tlj, rbi, rbj));

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для вычисления подматрицы
// сумма запроса за O (1) раз

  
// Функция предварительной обработки ввода mat [M] [N].
// Эта функция в основном заполняет aux [M] [N]
// такой, что aux [i] [j] хранит сумму
// элементов от (0,0) до (i, j)

function preProcess(&$mat, &$aux)

{

    $M = 4;

    $N = 5;

      

    // Копируем первую строку mat [] [] в aux [] []

    for ($i = 0; $i < $N; $i++)

        $aux[0][$i] = $mat[0][$i];

      

    // Делаем столбцы мудрой суммы

    for ($i = 1; $i < $M; $i++)

        for ($j = 0; $j < $N; $j++)

            $aux[$i][$j] = $mat[$i][$j] +

                           $aux[$i - 1][$j];

      

    // Сделать строку мудрой суммы

    for ($i = 0; $i < $M; $i++)

        for ($j = 1; $j < $N; $j++)

            $aux[$i][$j] += $aux[$i][$j - 1];

}

  
// AO (1) функция времени для вычисления суммы
// подматрица между (tli, tlj) и
// (rbi, rbj) используя встроенный aux [] []
// функцией предварительной обработки

function sumQuery(&$aux, $tli, $tlj, $rbi,$rbj)

{

    // результат теперь сумма элементов

    // между (0, 0) и (rbi, rbj)

    $res = $aux[$rbi][$rbj];

  

    // Удалить элементы между (0, 0)

    // и (tli-1, rbj)

    if ($tli > 0)

    $res = $res - $aux[$tli - 1][$rbj];

  

    // Удалить элементы между (0, 0)

    // и (rbi, tlj-1)

    if ($tlj > 0)

    $res = $res - $aux[$rbi][$tlj - 1];

  

    // Добавить aux [tli-1] [tlj-1] как элементы между (0, 0)

    // и (tli-1, tlj-1) вычитаются дважды

    if ($tli > 0 && $tlj > 0)

    $res = $res + $aux[$tli - 1][$tlj - 1];

  

    return $res;

}

  
// Код драйвера

$mat = array(array(1, 2, 3, 4, 6),

             array(5, 3, 8, 1, 2),

             array(4, 6, 7, 5, 5),

             array(2, 4, 8, 9, 4));

  

preProcess($mat, $aux);

  

$tli = 2;

$tlj = 2;

$rbi = 3;

$rbj = 4;

echo ("Query1: ");

echo(sumQuery($aux, $tli, $tlj, $rbi, $rbj));

  

$tli = 0;

$tlj = 0;

$rbi = 1;

$rbj = 1;

echo ("\nQuery2: ");

echo(sumQuery($aux, $tli, $tlj, $rbi, $rbj));

  

  

$tli = 1;

$tlj = 2;

$rbi = 3;

$rbj = 3;

echo ("\nQuery3: ");

echo(sumQuery($aux, $tli, $tlj, $rbi, $rbj));

  
// Этот код предоставлен Shivi_Aggarwal
?>

Выход:

Query1: 38
Query2: 11
Query3: 38

Источник: http://espressocode.top/amazon-interview-experience-set-241-1-5-years-experience/

Эта статья пополняемые Шивов Гупт. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Submatrix Sum Queries

0.00 (0%) 0 votes