RMQ на статическом 2D массиве в постоянное время

Question

RMQ на статическом 2D массиве в постоянное время

Ввод представляет собой массив (n*m 1<n,m< 1000), Я должен найти максимальный элемент в каждом подматрице size( a*b ),

Я пытался сделать это, повторяя x над n-a+1 а также y над m-j+1,

2D segment trees или же quad tree Это не достаточно быстро, так как количество запросов велико.
Я пытался продлить sparse table но не смог из-за нехватки места.
Я читал о решениях с Cartesian trees но нужен какой-то код, так как я не могу этого понять.

Пожалуйста, объясните решение, которое ответит на запрос в O(nm) время или в O(1) время по предварительным расчетам. Кроме того, входной массив является статическим.

Примечание: хотя я пытался sparse table, это может быть не правильно, поэтому не стесняйтесь опубликовать решение с ним.

Я Java кодер, поэтому реализация в Java или же c/c++ было бы замечательно.

Также это не дубликат, так как я много об этом искал, не найдя ничего подходящего.

1

arrays algorithm 2d rmq cartesian-tree

Источник

user6435928 07 июн '16 в 15:08

2 ответа

Решение

Я нашел ответ, чтобы он вычислил в O(mn) - все еще с небольшим предварительным вычислением - но на этот раз это легко O(mn.log(mn)) тоже: просто упорядочить список всех значений матрицы.

Предварительно вычисляют:

Первый шаг - просто построить упорядоченную структуру значений матрицы, скажем, M(A)затем используйте <algorithm>std::sort заказать эту структуру.

Получить максимум любой субматрицы `(a,b)`:

Чтобы получить максимум любой матрицы, просто начните с самой большой из предварительно вычисленной структуры M(A) и проверьте, находится ли он в пределах (a,b),

Если это так, то вы сделали
Остальное, возьмите следующий в M(A)

matrix.h

#ifndef myMatrix_JCHO
#define myMatrix_JCHO

typedef unsigned int u_it;
typedef std::pair<u_it, u_it> uup;

class Matrix
{
public:
    Matrix(u_it _n, u_it _m);
    Matrix(const Matrix& matr);
    Matrix& operator=(const Matrix& matr);
    ~Matrix();

    u_it getNumRows() ;
    u_it getNumCols() ;

    int getC(u_it i, u_it j);
    void setC(u_it i, u_it j, int v);
    void printMatrix();
    int maxSub(u_it a_i, u_it a_j, u_it b_k, u_it b_l);

private:
    u_it n, m;
    int **pC;

};

#endif

matrix.cpp

#include <iostream>
#include <string>
#include <sstream>

#include "matrix.h"

Matrix::Matrix(u_it _n, u_it _m) {
    n=_n;
    m=_m;
    //int k=0;
    pC = new int*[n];
    for (u_it i=0; i<n; ++i){
       pC[i]=new int[m];
       for(u_it j=0; j<m; ++j){
         pC[i][j]=rand()%1000;
       }
    }
}
Matrix::~Matrix(){
    for (u_it i=0; i<n; ++i){
        delete [] pC[i];
    }
    delete [] pC;
    std::cout << "matrix destroyed\n";
}
u_it Matrix::getNumRows() {
    return n;
}
u_it Matrix::getNumCols() {
    return m;
}
int Matrix::getC(u_it i, u_it j){
    return pC[i][j];
}
void Matrix::setC(u_it i, u_it j, int v){
    pC[i][j]=v;
}
void Matrix::printMatrix(){
    for (u_it i=0; i<n; ++i){
      std::cout << "row " <<i<<" [ ";
      for(u_it j=0; j<m; ++j){
        std::cout << pC[i][j] << '\t';
      }
      std::cout << "]\n";
    }
}

main.cpp

#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <vector>

#include "matrix.h"


// sort function for my vector of pair:
bool oMyV(std::pair<uup, int> x, std::pair<uup, int> y) { return (x.second > y.second); }

// check that p is within matrix formed by a and b
bool isIn_a_b(uup p, uup a, uup b){
    bool res = false;
    if (p.first >= a.first && p.first <= b.first) {
      if (p.second >= a.second && p.second <= b.second) {
        res = true;
      }
    }
    return res;
}

int main() {
    u_it n_rows, n_cols;
    std::cout << " enter number of rows:";
    std::cin >> n_rows;
    std::cout << " enter number of cols:";
    std::cin >> n_cols;
    std::cout << " pre-computing...\n";

    std::pair<uup, int> *ps;
    std::vector<std::pair<uup, int> > myV;
    Matrix * mat=new Matrix(n_rows,n_cols);
    // print to debug:
    mat->printMatrix();
    // "PRE" computation
    for (u_it i=0; i<n_rows; ++i) {
      for (u_it j=0; j<n_cols; ++j) {
        ps=new std::pair<uup, int>(std::make_pair(i,j), mat->getC(i,j));
        myV.push_back(*ps);
      }
    }
    std::sort(myV.begin(), myV.end(), oMyV);
    /* in case you want to print ordered valuet ordered valuess for debug */
    for (std::vector<std::pair<uup, int> >::iterator it=myV.begin(); it!=myV.end(); ++it) {
      std::cout << it->second << " at [" << it->first.first <<','<<it->first.second<< "]\n";
    }
    /**/

    // call to values
    bool byebye=false;
    uup a, b;

    do {
      std::cout << " enter i,:";     std::cin >> a.first;
      std::cout << " enter j,:";     std::cin >> a.second;
      std::cout << " enter k,:";     std::cin >> b.first;
      std::cout << " enter l,:";     std::cin >> b.second;

      std::vector<std::pair<uup, int> >::iterator it=myV.begin();
      std::cout << " a:["<<a.first<<','<<a.second<<"]-b:["<<b.first<<','<<b.second<<"] in ";
      std::cout << " M:[0,0]--:["<<n_rows-1<<','<<n_cols-1<<"]\n";
      // check validity:
      if (  isIn_a_b(a, std::make_pair(0,0), std::make_pair(n_rows-1, n_cols-1) )
         && isIn_a_b(b, std::make_pair(0,0), std::make_pair(n_rows-1, n_cols-1) )
         && (a.first <= b.first)
         && (a.second <= b.second)
         ) {
        while (! isIn_a_b(it->first, a, b) && it!=myV.end()){
          ++it;
        }
        std::cout << "Found:" << it->second << " at [" << it->first.first <<','<<it->first.second<< "]\n";
      } else {
        std::cout << "makes no sense. bye.\n";
        byebye=true;
      }
    } while (!byebye);
}

Makefile

(не забудьте: табулировать в Makefile)

OBJS = matrix.o main.o
CC = g++ -std=c++0x
DEBUG = -g
CFLAGS = -std=c++0x -Wall -c $(DEBUG)
LFLAGS = -std=c++0x -Wall $(DEBUG)
TARFILE =  ${HOME}/jcho/good/matrix.tar

p1 : $(OBJS)
        $(CC) $(LFLAGS) $(OBJS) -o p1

matrix.o: matrix.cpp matrix.h
        $(CC) $(CFLAGS) matrix.cpp

main.o: main.cpp matrix.h
        $(CC) $(CFLAGS) main.cpp

clean:
        \rm -f *.o *~ p1

tar:
        tar cfv  $(TARFILE) *.h *.cpp Makefile \
            p1 && \
            echo "tar $(TARFILE) created successfuly."

0

Источник

user6019417 29 июн '16 в 12:34

Другие вопросы по тегам arrays algorithm 2d rmq cartesian-tree

user6019417 09 июн '16 в 12:56 2016-06-09 12:56 · Accepted Answer · 2016-06-09 12:56

Количество возможностей:

(Из номера подматрицы размера AxB в матрице размера MxN)
В матрице size (m*n), имеются (n-A+1)*(m-B+1) разные матрицы size (A*B),
Таким образом, общее количество возможных входных данных для вашей функции sum((n-A+1)*(m-B+1)) где A=1..n а также B=1..m,

РЕДАКТИРОВАТЬ: Это становится настолько огромным, когда м =1000.
O(m^2n^2) является O(1000^4)... 1 триллион... это не поместится в памяти моего маленького компьютера:)

Состав:

Я предлагаю вам построить hashmap что вы просто индексируете границы вашей матрицы:
Строка построена из a=M(i,j), b=M(k,l) где 0< i < k <(n+1) а также 0< j < l <(m+1)

Например, вы можете построить это так: aHashMap("["+i+","+j+"].["+k+","+l+"]")

Предварительное вычисление:

Имейте функцию, которая вычисляет максимум данной матрицы (a[i,j],b[k,l]) - скажем myMax(i,j,k,l), Я предполагаю, что нет смысла показывать вам, как.

Тогда это легко (извините, я не могу легко что-то скомпилировать, поэтому пока я даю только принцип):

для I = 1 до N-1 сделать
    для j=1 до m-1 сделать 
        для к = я к п сделать
            для l=j до m do 
                aHashMap("["+i+","+j+"].["+k+","+l+"]") = myMax(i,j,k,l)
            следующий
        следующий
    следующий
следующий

Это O(n^4), но при условии, что он до вычисления, нет никакого смысла, он просто делает вашу программу больше и больше при хранении aHashMap,

Хорошо знать

Такая проблема также, кажется, широко рассматривается на http://cs.stackexchange.com/; например, тот или другой... так что этот SE может представлять интерес для ОП.

Реализация этого наивного подхода:

С 99 x 95 он уже дает миллионы возможностей для предварительных вычислений, занимая около 3 000 ГБ ОЗУ!

$ ./p1
 enter number of rows:99
 enter number of cols:95
pre-computing...
hashmap ready with 22572000 entries.

matrix.h

#ifndef myMatrix_JCHO
#define myMatrix_JCHO

typedef unsigned int u_it;

class Matrix
{
public:
    Matrix(u_it _n, u_it _m);
    Matrix(const Matrix& matr);
    Matrix& operator=(const Matrix& matr);
    ~Matrix();

    u_it getNumRows() ;
    u_it getNumCols() ;

    int getC(u_it i, u_it j);
    void setC(u_it i, u_it j, int v);
    void printMatrix();
    int maxSub(u_it a_i, u_it a_j, u_it b_k, u_it b_l);

private:
    u_it n, m;
    int **pC;

};

#endif

matrix.cpp

#include <iostream>
#include <string>
#include <sstream>

#include "matrix.h"

Matrix::Matrix(u_it _n, u_it _m) {
    n=_n;
    m=_m;
    int k=0;
    pC = new int*[n];
    for (u_it i=0; i<n; ++i){
       pC[i]=new int[m];
       for(u_it j=0; j<m; ++j){
         pC[i][j]=++k;
       }
    }
}
Matrix::~Matrix(){
    for (u_it i=0; i<n; ++i){
        delete [] pC[i];
    }
    delete [] pC;
    std::cout << "matrix destroyed\n";
}
u_it Matrix::getNumRows() {
    return n;
}
u_it Matrix::getNumCols() {
    return m;
}
int Matrix::getC(u_it i, u_it j){
    return pC[i][j];
}
void Matrix::setC(u_it i, u_it j, int v){
    pC[i][j]=v;
}
void Matrix::printMatrix(){
    for (u_it i=0; i<n; ++i){
      std::cout << "row " <<i<<" [ ";
      for(u_it j=0; j<m; ++j){
        std::cout << pC[i][j] << '\t';
      }
      std::cout << "]\n";
    }
}

// Return max of submatrix a(i,j); b(k,l)
int Matrix::maxSub(u_it a_i, u_it a_j, u_it b_k, u_it b_l) {
   int res = -100000;
   if (a_i<=b_k && a_j<=b_l && b_k<n && b_l<m) {
     for (u_it i=a_i; i<=b_k; ++i){
       for(u_it j=a_j; j<=b_l; ++j){
         res= (pC[i][j]>res)? pC[i][j] : res;
       }
     }
   } else {
     std::cout << "invalid arguments: out of bounds\n";
     return -100000;
   }

   return res;
}

main.cpp

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <cassert>

#include "matrix.h"

std::string hashKey(u_it a_i, u_it a_j, u_it b_k, u_it b_l) {
    std::stringstream ss;
    ss << "max(a[" << a_i << "," << a_j << "],b[" << b_k << "," << b_l << "]";
    return ss.str();
}

int main() {
    u_it n_rows, n_cols;
    std::cout << " enter number of rows:";
    std::cin >> n_rows;
    std::cout << " enter number of cols:";
    std::cin >> n_cols;
    std::cout << " pre-computing...\n";

    std::map<std::string, int> myHMap;
    Matrix * mat=new Matrix(n_rows,n_cols);
    //mat->printMatrix();
    // "PRE" computation
    for (u_it i=0; i<n_rows; ++i) {
      for (u_it j=0; j<n_cols; ++j) {
        for (u_it k=i; k<n_rows; ++k) {
          for (u_it l=j; l<n_cols; ++l) {
            //std::cout <<"max(a["<<i<<","<<j<<"],b["<<k<<","<<l<<"]"<< mat->maxSub(i, j, k, l) <<'\n';
            //std::cout << mat->hashKey(i, j, k ,l) <<" -> " <<  mat->maxSub(i, j, k, l)  <<'\n';
            myHMap[hashKey(i, j, k ,l)] = mat->maxSub(i, j, k, l);
          }
        }
      }
    }
    std::cout << " hashmap ready with "<<  myHMap.size() <<" entries.\n";
    // call to values
    u_it cw_i, cw_j, cw_k, cw_l;
    cw_i=0;
    std::string hKey;
    while (cw_i < n_rows+1) {
      std::cout << " enter i,:";
      std::cin >> cw_i;
      std::cout << " enter j,:";
      std::cin >> cw_j;
      std::cout << " enter k,:";
      std::cin >> cw_k;
      std::cout << " enter l:";
      std::cin >> cw_l;
      hKey = hashKey(cw_i, cw_j, cw_k, cw_l);
      std::map<std::string, int>::iterator i = myHMap.find(hKey);
      assert(i != myHMap.end());
      std::cout << i->first <<" -> " <<  i->second  <<'\n';
    }
}

делать

g++ -std=c++0x  -std=c++0x -Wall -c -g matrix.cpp
g++ -std=c++0x  -std=c++0x -Wall -c -g main.cpp
g++ -std=c++0x  -std=c++0x -Wall -g matrix.o main.o -o p1

RMQ на статическом 2D массиве в постоянное время

2 ответа

Количество возможностей:

Состав:

Предварительное вычисление:

Хорошо знать

Реализация этого наивного подхода:

Предварительно вычисляют:

Получить максимум любой субматрицы (a,b):

matrix.h

matrix.cpp

main.cpp

Makefile

Получить максимум любой субматрицы `(a,b)`: