Tính tổng đoạn con
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Java
2.0s
Python
2.0s
Giới hạn bộ nhớ:
256M
Java
1G
Python
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, JS, Pascal, PHP, Python, Ruby
Bạn được cho một mảng gồm có n số nguyên dương ~a_1, a_2, a_3,…, a_n~ và ~Q~ truy vấn. Có 2 loại truy vấn như sau:
Loại truy vấn thứ nhất: Thay thế giá trị thứ ~x~ trong mảng thành ~val~, tức là ~a[x]=val~
Loại truy vấn thứ hai: In ra tổng trong đoạn từ ~a[l]~ tới ~a[r]~ ~( 1<=l<=r<=n)~
Input:
Dòng đầu tiên của input chứa số nguyên ~n (1 \leq n \leq 10^5)~ và số nguyên ~q(1 \leq q \leq 10^5)~
Dòng tiếp theo chứa n số nguyên ~a[i] (1 \leq i \leq n , 1\leq a[i] \leq 10^6)~
Các dòng tiếp theo là các Q truy vấn theo 2 dạng:
1 x val: tương ứng với loại truy vấn thứ nhất2 l r: tương ứng với loại truy vấn thứ hai
Output:
- Hãy in ra kết quả khi thực hiện các truy vấn loại 2, mỗi kết quả trên một dòng
Sample Input 1
5 4
5 10 90 100 1
2 1 3
1 2 2
2 1 4
2 3 5
Sample Output 1
105
197
191
Chia độ khó
| Độ khó | Điều kiện |
|---|---|
| Dễ (40% tổng số điểm) | ~1 \leq n \leq 100~ và ~1 \leq q \leq 100~ |
| Trung bình (30% tổng số điểm) | ~1 \leq n \leq 1000~ và ~1 \leq q \leq 1000~ |
| Khó (30% tổng số điểm) | ~1 \leq n \leq 10^5~ và ~1 \leq q \leq 10^5~ |
Bình luận
Ad cho mình hỏi bài này ngoài segment tree thì còn cách nào khác không ạ?
dùng thuật toán căn n