Bài này chúng ta vẫn có thể giải bằng segment tree, nhưng ở đây chúng ta sẽ dùng kĩ thuật chia căn để giải. Ý tưởng như sau:

Lời giải

- Ta chia dãy có độ dài ~n~ thành ~\sqrt{n}~ đoạn có độ dài ~\sqrt{n}~. Đặt ~\text{sum_block[i] = tổng của đoạn thứ i}~ trong số ~\sqrt{n}~ đoạn được chia.

- Khi cập nhật truy vấn ~1~ ta đổi giá trị tại vị trí thứ ~k~ ta gán thành ~a[k] = u~ và cập nhật lại ~\text{sum_block[id]}~ với ~id~ là chỉ số của đoạn chứa phần tử thứ ~k~.

- Khi trả lời truy vấn ~2~, ta có 2 trường hợp cần xét:

1. Trường hợp ~l, r~ ở trong hai đoạn khác nhau trong số các đoạn đã chia:

- Ta sẽ duyệt qua tất cả các đoạn nằm hoàn toàn trong đoạn ~[l,r]~, khi các đoạn này ghép lại ta sẽ tính được đáp án cho đoạn ~[l_1, r_1]~ với ~l \le l_1 \le r_1 \le r~, sau đó ta chỉ cần duyệt trâu để lần lượt cộng các phần tử ~a[i], \forall i \in [l, l_1) \cup (r_1, r]~.

2. Trường hợp khi ~l, r~ nằm trong cùng một đoạn:

- Ta sẽ duyệt trâu qua các phần ~a[i], \forall i \in [l, r]~ để tính kết quả.

Chứng minh thuật toán

- Ở truy vấn ~1~, ta hoàn toàn có thể cập nhật như đã nêu trên trong ~o(1)~.

- Ở truy vấn ~2~, nhận thấy: + Khi ta duyệt qua các phần tử ở trong ~1~ ta chỉ duyệt qua tối đa ~\sqrt{n}~ phần tử.

+ Khi ta phải duyệt qua các đoạn, số đoạn ta đã chia là ~\sqrt{n}~ đoạn, nên ta cũng chỉ duyệt qua tối đa ~sqrt{n}~ lần.

- Vậy khi ta trả lời truy vấn ~2~ sẽ tốn ~o( \sqrt{n})~ nên với ~q~ truy vấn, độ phức tạp sẽ là ~o(\sqrt{n} \cdot q)~ và với chi phí chuẩn là ~o(n)~ cho việc chia đoạn và tính tổng của mảng ~sum_block~. Nên độ phức tạp tổng sẽ là ~O(\sqrt{n} \cdot q + n)~.