Bài toán truy vấn tổng

Tác giả:

Dạng bài

Điểm: 400 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng gồm \(N\) phần tử \(a[1],a[2],...,a[N]\) và có \(T\) truy vấn có dạng như sau:

\(1\text{ }l\text{ }r\): In ra tổng tất cả các phần tử thuộc đoạn \([l,r]\)
\(2\text{ }x\text{ }y\): Thay giá trị tại vị trí thứ \(x\) thành \(y\) (tức là gán \(a[x]=y\))

Dòng thứ nhất chứa hai số nguyên \(N,T\)
Dòng thứ hai chứa \(N\) số nguyên \(a[1],a[2],...,a[N]\) \((1\leq a_i\leq 10^5)\)
\(T\) dòng tiếp theo chứa \(T\) truy vấn: \(1 \text{ }l\text{ }r\) \((1\leq l\leq r\leq n)\) hoặc \(2\text{ }x\text{ }y\) \((1\leq x\leq N, 1\leq y\leq 10^4)\)

Test 1

Input

Output

5
6

Bình luận