ข้อนี้เป็นโจทย์ที่ใช้ 2D rectangle sum ทั่วไป แนะนำให้อ่าน tutorial เรื่อง 2D rectangle sum ก่อนที่จะอ่านเฉลยด้านล่าง

สรุปโจทย์สั้นๆคือ มีของอยู่ $n$ ชิ้นซึ่งแต่ละชิ้นจะระบุพิกัดบนตารางอยู่ มีอยู่ $m$ โดยที่คำถามที่ $i$ อยุ่ในลักษณะ $(x_i, y_i, k_i)$ ซึ่งถามว่าในสี่เหลี่ยมจตุรัสที่มุมล่างซ้ายอยู่ที่ $(x_i - k_i, y_i - k_i)$ และมุมบนขวาที่ $(x_i + k_i, y_i + k_i)$ มีอยู่ของอยู่กี่ชิ้น

นิยาม $S[i][j]$ เท่ากับจำนวนชิ้นของที่อยู่ในสี่เหลี่ยมที่มีมุมล่างซ้ายที่ $(0,0)$ และมุมบนขวาที่ $(i, j)$ เราสามารถคำนวณทุกๆ $S[i][j]$ ไว้ล่วงหน้าโดยคำนวณคำตอบ $S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j]$ โดยที่ $A[i][j]$ เป็น 1 ก็ต่อเมื่อมีของอยู่ที่พิกัด $(i, j)$

ในแต่ละคำถาม คำตอบจะเท่ากับ $S[x_i + k_i][y_i + k_i] - S[x_i + k_i][y_i - k_i - 1] - S[x_i - k_i - 1][y_i + k_i] + S[x_i - k_i - 1][y_i - k_i - 1]$ สิ่งที่ควรระวังคือ ไม่ให้ค่า index อยู่นอก range $[0, 1000]$ ถ้าหากเป็นเช่นนั้นให้ปรับค่าเป็น 0 หรือว่า 1000 ได้เลยถ้าหากต่ำกว่า 0 หรือมากกว่า 1000

เนื่องจากการคำนวณ $S[i][j]$ ใช้เวลา $O(n^2)$ และการตอบคำถามใช้เวลา $O(m)$ อัลกอริทึมนี้ใช้เวลาโดยรวมแล้วเท่ากับ $O(n^2 + m)$