Kho Báu Hang Động

Buổi 27 — Segment Tree cơ bản
Points
10
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Một hang động có N hầm chứa vàng, hầm thứ i có a_i thỏi vàng. Thỉnh thoảng thợ mỏ thay đổi số vàng của một hầm, và bạn cần cho biết tổng số vàng trong một dãy hầm liên tiếp.

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q. Dòng thứ hai chứa N số nguyên a_1..a_N. Q dòng tiếp theo, mỗi dòng là một trong hai dạng:

  • 1 i x: gán a_i = x.
  • 2 l r: truy vấn trên đoạn [l, r].
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra tổng a_l + ... + a_r.

Ví dụ
Input Output
5 4\n2 4 8 4 8\n1 2 8\n1 3 8\n1 2 6\n1 2 0
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • 0 ≤ a_i, x ≤ 10^9
Draft saved