設計數據結構以有效查詢子矩陣的最小公倍數

Question

問題來自面試。有一個整數NxN矩陣，N可能在10^4以上。問題是如何設計一個輔助數據結構來有效地得到N×N矩陣的任何子矩形矩陣的最小公倍數。使用的空間不應該超過2xNxN或3xNxN，我不記得它清楚，但我們不要太嚴格限制空間。

Answer 1

我認爲Segment tree會有所幫助。讓我們考慮一個更容易的問題，在那裏給出一個數組A[N]和N整數，比查詢任何子數組的最小公倍數。使用分段樹，將每個節點[l, r]與最小公倍數相關聯。每個查詢常量 O(lnN)時間和總空間大約是2*N。

對於矩陣，使用2維分段樹。以下是query gcd in matrix的解決方案，與您的問題類似。