ปัญหา
อาร์เรย์ nums ขนาด n, Queries (p_i, q_i) ตอบ: Sum ของ nums[j] ที่ p_i ≤ j < n และ (j - p_i) หาร q_i ลงตัว Mod 10^9+7
ตัวอย่าง
nums = [2,3,4,5,6,7,8,9,10], Queries = [(2,5),(7,3),(6,4)]
Output: [13, 9, 8]
Query (2,5): j=2,7 → nums[2]+nums[7] = 4+9 = 13
อัลกอริทึม (Sqrt Decomposition / Precomputation)
- Precompute สำหรับ Step Size k ≤ √n: P[k][i] = Sum ของ nums[i], nums[i+k], nums[i+2k], ...
- สำหรับ Query (p, k): ถ้า k < √n → คืน P[k][p] ทันที
- ถ้า k ≥ √n → Loop ตรงๆ (High Step = จำนวน Terms น้อย ≤ √n)
ตัวอย่างโค้ด
def solve(A, Q):
n, M = len(A), 10**9 + 7
m = int(n**0.5) + 2
P = [A[:] for _ in range(m)]
for i in range(1, m):
for j in range(n - 1, -1, -1):
if i + j < n:
P[i][j] = (P[i][j] + P[i][i + j]) % M
return [P[k][b] if k < m else sum(A[b::k]) % M for b, k in Q]
print(solve([2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)])) # [13, 9, 8]ความซับซ้อน
- Preprocess: O(n√n)
- Query: O(1) สำหรับ k < √n, O(√n) สำหรับ k ≥ √n
- Space: O(n√n)
