Để giải bài này, chúng ta cần 2 ý tưởng. Một trong số đó được là sub 2.

Sub 2

Để ý rằng nếu ta tính hết đáp số cho các cặp \((k, p)\) có thể thì độ phức tạp là \(O(n^2)\) vì có \(n^2\) cặp như vậy. Tuy nhiên, ta không cần tính hết, chỉ cần tính sẵn vài cặp, còn những cặp khác có thể đợi đến lúc đọc truy vấn mới tính. Vấn đề là cần tính sẵn những cặp nào?

Để ý rằng, \(s(p, k) = a_p + a_{p+k} + a_{p+2k} + ...\) không có quá nhiều số nếu \(k\) lớn, nhưng lại có rất nhiều số hạng nếu \(k\) nhỏ. Như vậy, ta chỉ cần tính sẵn các cặp có \(k\) nhỏ. Còn các cặp có \(k\) lớn sẽ được tính lúc hỏi.

Giả sử ta tính hết các \(s(p, k)\) với \(k \leq C\). Khi đó ta cần \(O(nC)\). Để ý \(s(p, k) = s(p - k, k) - a[p - k]\).

Các cặp \((p, k)\) có \(k > C\) sẽ được tính khi cần trả lời. Số lượng số hạng mỗi truy vấn là không quá \(\dfrac{n}{C}\). Ta cần tối đa \(O(\dfrac{qn}{C})\)

Như vậy tổng độ phức tạp là \(O(nC + \dfrac{qn}{C})\) Ta sẽ chọn \(C\) sao cho số này nhỏ nhất có thể. Cách đơn giản nhất là cho 2 số hạng bằng nhau, tức là \(C = \sqrt{q}\). Độ phức tạp là \(O(n\sqrt{q})\).

Sub 3:

Ta sẽ tiếp tục sử dụng ý tưởng giải quyết hai bài toán riêng cho \(k \leq C\) và \(k > C\).

Trường hợp 1: \(k > C\)
Ta có thể giải hoàn toàn như trên. Độ phức tạp là \(O(\dfrac{qn}{C})\). Thao tác cập nhật chỉ đơn giản là cho \(a[i] = u\).

Trường hợp 2: \(k \leq C\)
Vấn đề nảy sinh lúc này là các \(s(p, k)\) tính sẵn sẽ bị thay đổi sau mỗi thao tác cập nhật. Đầu tiên hãy thử xem, nếu bài toán chỉ có \(k = 1\) hoặc \(2\) thì giải quyết thế nào?

• \(k = 1\):
• Cập nhật \(a[i] = u\)
• Tính tổng \(a_p + a_{p + 1} + ... + a_{n}\)
• Đây chính là ứng dụng cơ bản của BIT
• \(k = 2\):
• Cập nhật \(a[i] = u\)
• Tính tổng \(a_p + a_{p + 2} + ...\)
• Để ý rằng có hai dãy \(a_1, a_3, a_5, ...\) và \(a_2, a_4, ...\) không liên quan nhau. Như vậy nếu ta tách chúng ra thành hai dãy rời nhau thì sẽ quy về trường hợp \(k = 1\) với hai cây BIT.

Vậy nếu \(k\) vừa có thể bằng \(1\) vừa có thể bằng \(2\) thì sao? Ta cần cả 3 cây BIT, một cho \(k = 1\) và hai cho \(k = 2\). Thao tác cập nhật cần cập nhật cho cây BIT của \(k = 1\) và một trong hai cây BIT của \(k = 2\). Thao tác trả lời ta sẽ gọi một cây BIT của \(k\).

Ý tưởng trên có thể tổng quát cho mọi \(k \leq C\). Với mỗi \(k\), ta lưu \(k\) cây BIT độ dài \(\dfrac{n}{k}\).

• Dựng cây tốn \(O(nC)\)
• Thao tác cập nhật cần cập nhật cho \(C\) cây BIT, dựa theo \(p \% k\). Độ phức tạp là \(O(qC \log n)\)
• Thao tác trả lời sẽ gọi truy vấn từ một cây BIT của \(k\). Độ phức tạp là \(O(q \log n)\). Không đáng kể so với thao tác cập nhật

Như vậy tổng độ phức tạp là \(O(qC \log n + q\dfrac{n}{C})\). Lúc này, ta chọn \(C = \sqrt{\dfrac{n}{\log n}}\) Độ phức tạp là \(O(q * \sqrt{n \log n})\).

Thực tế, \(C\) có thể được chọn khoảng 10 tới 100 đều có thể AC. Vì đây là cuộc thi online, các bạn có thể nộp nhiều lần với nhiều \(C\) khác nhau.