原文轉(zhuǎn)自：http://www.hankcs.com/program/algorithm/imos_method.html
但原文示例有誤，應(yīng)修改為一下：
在“怪物地圖”的例子中思想與代碼有誤，應(yīng)改為：左上角+1卡睦，右上角右側(cè)-1本慕，左下角下方-1踏堡，右下角右下方+1碌燕；若超出tiles則沒(méi)有+1或-1折汞；根據(jù)圖示倔幼，怪物種類(lèi)應(yīng)該是3種，坐標(biāo)應(yīng)該為：
// 左下角坐標(biāo)
int b[] = {3,4,5};
int c[] = {0,1,2};
// 右上角坐標(biāo)
int a[] = {0,3,2};
int d[] = {3,2,5};
修改后代碼為
public void monsterMap() {
int h=6;
int w=6;
int n=3;
// 左下角坐標(biāo)
int b[] = {3,4,5};
int c[] = {0,1,2};
// 右上角坐標(biāo)
int a[] = {0,3,2};
int d[] = {3,2,5};
int[][] tiles = new int[h][w];
//影響力
for (int i = 0; i < n; i++) {
setTiles(tiles, a[i], c[i], +1);
setTiles(tiles, b[i]+1, d[i]+1, +1);
setTiles(tiles, a[i], d[i]+1, -1);
setTiles(tiles, b[i]+1, c[i], -1);
}
//橫向累加
for (int i = 0; i < h; i++) {
for (int j = 1; j < w; j++) {
tiles[i][j] += tiles[i][j-1];
}
}
//縱向累加
for (int i = 0; i < w; i++) {
for (int j = 1; j < h; j++) {
tiles[j][i] += tiles[j-1][i];
}
}
//查詢(xún)最大值
int max=0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
max = Math.max(tiles[i][j], max);
}
}
System.out.println(max);
}
private void setTiles(int[][] tiles, int h, int w, int v) {
if (h >= tiles.length || w >= tiles[h].length) {
return ;
}
tiles[h][w] = v;
}
以下為原文部分
在解AOJ 0531 Paint Color時(shí)爽待，學(xué)到了一個(gè)累積和的妙用——imos法损同，由于原文是日語(yǔ)，所以特意翻譯過(guò)來(lái)鸟款。值得一提的是膏燃，作者Kentaro Imajo跟鄙人同齡，卻已取得如此多的成就何什，而鄙人一無(wú)所成蹄梢，實(shí)在汗顏。
imos法
imos法是將累積和算法拓展到多次元富俄、高次空間的方法。雖然程序競(jìng)賽中出題最多不過(guò)2次元1次而咆，但是2012年Kentaro Imajo將其用于高次元高次空間霍比，在信號(hào)處理/圖像處理領(lǐng)域取得了成就。
基礎(chǔ)imos法
最簡(jiǎn)單的imos法是1次元0次系數(shù)的求解思想暴备。如圖悠瞬，有三個(gè)俄羅斯方塊在一起，懸空的部分會(huì)掉下去，求從左到右的高度浅妆？這個(gè)高度就是橫坐標(biāo)固定時(shí)望迎，上面矩形高度之和。這就是最簡(jiǎn)單的imos法凌外。
例題
你在經(jīng)營(yíng)一個(gè)咖啡廳辩尊，你的咖啡廳里每個(gè)客人在S_i時(shí)刻進(jìn)店，E_i時(shí)刻出店康辑。求店里最多有多少客人摄欲？（客人最多C個(gè)，時(shí)刻在T內(nèi)疮薇。如果有多人同時(shí)進(jìn)店出店胸墙，先算出店的人）。
樸素的解法
樸素的思想是按咒，計(jì)算每個(gè)時(shí)刻客戶(hù)的數(shù)量迟隅，從中找出最大值。但是励七，復(fù)雜度是O(CT)
1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
5. #define C 4
6. #define T 10
7. // 每個(gè)客人的進(jìn)入時(shí)間
8. int S[C] = { 1, 3, 5, 7 };
9. // 每個(gè)客人的離開(kāi)時(shí)間
10. int E[C] = { 2, 8, 6, 8 };
11. // 店里的人數(shù)
12. int table[T];
14. ///////////////////////////SubMain//////////////////////////////////
15. int main(int argc, char *argv[])
16. {
17. memset(table, 0, sizeof(table));
18. for (int i = 0; i < C; i++)
19. {
20. // 從時(shí)間 S[i] 到 E[i] - 1 店里人數(shù)計(jì)數(shù)加一
21. for (int j = S[i]; j < E[i]; j++)
22. {
23. table[j]++;
24. }
25. }
26. // 找最大値
27. cout<< *max_element(table, table + T) << endl;
28. system("pause");
29. return 0;
30. }
31. ///////////////////////////End Sub//////////////////////////////////
imos法解法
imos法的基本方向是智袭，只統(tǒng)計(jì)出入店時(shí)刻的人數(shù)變化（我個(gè)人理解相當(dāng)于求導(dǎo)），入店+1呀伙，出店-1补履。最終統(tǒng)計(jì)的時(shí)候，需要將每個(gè)時(shí)刻加上前一個(gè)時(shí)刻的統(tǒng)計(jì)量（我個(gè)人理解相當(dāng)于求積分）剿另，其中的最大值就是所求箫锤。記錄復(fù)雜度O(C)，累加復(fù)雜度O(T)雨女，所以整體復(fù)雜度O(C+T)谚攒。
1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
5. #define C 4
6. #define T 10
7. // 每個(gè)客人的進(jìn)入時(shí)間
8. int S[C] = { 1, 3, 5, 7 };
9. // 每個(gè)客人的離開(kāi)時(shí)間
10. int E[C] = { 2, 8, 6, 8 };
11. // 店里的人數(shù)
12. int table[T];
14. ///////////////////////////SubMain//////////////////////////////////
15. int main(int argc, char *argv[])
16. {
17. memset(table, 0, sizeof(table));
18. for (int i = 0; i < C; i++)
19. {
20. table[S[i]]++; // 入店+1
21. table[E[i]]--; // 出店-1
22. }
23. // 累加
24. for (int i = 1; i < T; i++)
25. {
26. table[i] += table[i - 1];
27. }
28. // 找最大値
29. cout<< *max_element(table, table + T) << endl;
30. system("pause");
31. return 0;
32. }
33. ///////////////////////////End Sub//////////////////////////////////
推廣到二次元
imos相對(duì)于樸素方法的一個(gè)優(yōu)點(diǎn)就是隨著次元增大復(fù)雜度的降低越明顯。
例題
你在玩一個(gè)抓怪獸的游戲氛堕，現(xiàn)在你面前是一張W*H的地圖馏臭，地圖里有N種怪物。怪物i只會(huì)在左下角為（B_i,C_i）讼稚，右上角為(A_i,D_i)的矩形區(qū)域內(nèi)出現(xiàn)括儒。求單位區(qū)域內(nèi)最多有多少種怪獸？
樸素解法
樸素的解法就是計(jì)算每一個(gè)單位區(qū)域內(nèi)出現(xiàn)的怪獸數(shù)锐想，然后找出最大值帮寻。復(fù)雜度是O（NWH）。
1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
4. #define W 6
5. #define H 6
6. #define N 4
7. // 左下角坐標(biāo)
8. int B[N] = {3,4,3,5,};
9. int C[N] = {0,1,2,2,};
10. // 右上角坐標(biāo)
11. int A[N] = {0,3,2,2,};
12. int D[N] = {3,2,3,5,};
13. // 地圖上的分布結(jié)果
14. int tiles[H][W];
16. ///////////////////////////SubMain//////////////////////////////////
17. int main(int argc, char *argv[])
18. {
19. memset(tiles, 0, sizeof(tiles));
20. for (int i = 0; i < N; i++)
21. {
22. // 怪獸 i 出現(xiàn)的范圍 [(A[i],C[i]), (B[i],D[i])) 內(nèi)的計(jì)數(shù)加一
23. for (int y = C[i]; y < D[i]; y++)
24. {
25. for (int x = A[i]; x < B[i]; x++)
26. {
27. tiles[y][x]++;
28. }
29. }
30. }
31. // 求最大値
32. cout<< *max_element(tiles[0], tiles[0] + H * W) << endl;
33. system("pause");
34. return 0;
35. }
36. ///////////////////////////End Sub//////////////////////////////////
imos法解法
此例思想與代碼有誤,修改方法見(jiàn)文字開(kāi)頭
矩形的左上角 (A[i],C[i]) +1 赠摇，右上角 (A[i],D[i]) ?1固逗，左下角 (B[i],C[i]) ?1 浅蚪，右下角(B[i],D[i]) +1 ，統(tǒng)計(jì)最終結(jié)果之前累加烫罩。加一減一 O(N)惜傲，累加(WH) 整體復(fù)雜度 O(N+WH) 。
1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
4. #define W 6
5. #define H 6
6. #define N 4
7. // 左下角坐標(biāo)
8. int B[N] = {3,4,3,5,};
9. int C[N] = {0,1,2,2,};
10. // 右上角坐標(biāo)
11. int A[N] = {0,3,2,2,};
12. int D[N] = {3,2,3,5,};
13. // 地圖上的分布結(jié)果
14. int tiles[H][W];
16. ///////////////////////////SubMain//////////////////////////////////
17. int main(int argc, char *argv[])
18. {
19. memset(tiles, 0, sizeof(tiles));
20. // 影響力計(jì)算 (圖 3)
21. for (int i = 0; i < N; i++)
22. {
23. tiles[C[i]][A[i]]++;
24. tiles[C[i]][B[i]]--;
25. tiles[D[i]][A[i]]--;
26. tiles[D[i]][B[i]]++;
27. }
28. // 橫向累積和 (圖 4, 5)
29. for (int y = 0; y < H; y++)
30. {
31. for (int x = 1; x < W; x++)
32. {
33. tiles[y][x] += tiles[y][x - 1];
34. }
35. }
36. // 縱向累積和 (圖 6, 7)
37. for (int y = 1; y < H; y++)
38. {
39. for (int x = 0; x < W; x++)
40. {
41. tiles[y][x] += tiles[y - 1][x];
42. }
43. }
45. cout<< *max_element(tiles[0], tiles[0] + H * W) << endl;
46. system("pause");
47. return 0;
48. }
49. ///////////////////////////End Sub//////////////////////////////////
圖三：影響力計(jì)算
圖四：橫向累加
圖五：橫向累加結(jié)果
圖六：縱向累加
圖七：縱向累加結(jié)果
更高級(jí)的用法
暫時(shí)用不到贝攒，記錄一個(gè)地址盗誊，有空再看。
