Range Sum Query 2D - ไม่เปลี่ยนรูปใน C ++

สมมติว่าเรามีเมทริกซ์ 2 มิติที่เรียกว่าเมทริกซ์ เราต้องหาผลรวมขององค์ประกอบภายในสี่เหลี่ยมผืนผ้าที่กำหนดโดยมุมซ้ายบนโดยใช้ (row1, col1) และมุมขวาล่างโดยใช้ ( row2, col2).

ดังนั้นหากเมทริกซ์เป็นเหมือน −

สี่เหลี่ยมด้านบนที่มีสีน้ำเงินกำหนดโดย (2,1) และ (4,3) ซึ่งมีผลรวม 8

ดังนั้นหากเราดำเนินการค้นหาบางอย่างเช่น sumRegion(2, 1, 4, 3), sumRegion(1, 1, 2, 2), sumRegion(1, 2, 2, 4) สิ่งเหล่านี้จะส่งกลับ 8, 11, 12 ตามลำดับ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดเมทริกซ์ที่เรียกว่า dp

• เริ่มงานได้ดังนี้

• n :=จำนวนแถว ถ้า n เป็น 0 ให้กลับ

• m :=จำนวนคอลัมน์

• dp :=เมทริกซ์ขนาดอื่น n x m

• สำหรับฉันอยู่ในช่วง 0 ถึง n

  • สำหรับ j ในช่วง 0 ถึง m

    • เมื่อ j – 1 <0 ให้ตั้งค่า dp[i, j] เป็น matrix[i, j] หรือตั้งค่าเป็น (dp[i, j - 1] + matrix[i, j])

• สำหรับฉันอยู่ในช่วง 1 ถึง n

  • สำหรับ j ในช่วง 0 ถึง m

    • เพิ่ม dp[i, j] โดย dp[i – 1, j]

• สำหรับวิธีการสืบค้น จะใช้ row1, col1, row2, col2

• ret :=dp[row2, col2]

• sub1 :=0 เมื่อ row1 – 1 <0 มิฉะนั้น จะเป็น dp[row1 – 1, col2]

• sub2 :=0 เมื่อ col1 – 1 <0 มิฉะนั้นจะเป็น dp[row2, col1 - 1]

• ถ้าแถวที่ 1 – 1 <0 หรือ col1 – 1 <0 แล้ว

  • เพิ่ม :=0

• มิฉะนั้นให้เพิ่ม :=dp[row1 – 1, col1 – 1]

• return ret – sub1 – sub2 + เพิ่ม

ตัวอย่าง(C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include ใช้เนมสเปซ std;คลาส NumMatrix { สาธารณะ:เวกเตอร์ > dp; NumMatrix(เวกเตอร์<เวกเตอร์>&เมทริกซ์) { int n =matrix.size(); if(!n) ส่งคืน; int m =เมทริกซ์[0].size(); dp =เวกเตอร์ <เวกเตอร์ >(n, เวกเตอร์  (m)); for(int i =0; i > mat ={{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1, 5},{4,1,0,1,7},{1,0,3,0,5}}; NumMatrix ob(เสื่อ); ศาล < 
อินพุต
 <ก่อน>[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7 ],[1,0,3,0,5]]sumRegion(2,1,4,3)sumRegion(1,1,2,2)sumRegion(1,2,2,4)

ผลลัพธ์

81112