Phiên bản mảng và tổng đoạn

Buổi 30 — Persistent Segment Tree
Points
10
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho mảng $a_1,\dots,a_n$ (phiên bản $0$). Bạn cần xử lý $q$ thao tác; mỗi thao tác loại $1$ tạo ra phiên bản mới có số hiệu bằng số phiên bản hiện có (lần lượt $1,2,\dots$).

  • 1 v i x: tạo phiên bản mới từ phiên bản $v$ bằng cách cộng $x$ vào $a_i$.
  • 2 v l r: in ra tổng $a_l+\dots+a_r$ của phiên bản $v$.
Dữ liệu vào

Dòng đầu: $n, q$. Dòng hai: $n$ số nguyên $a_i$. Tiếp theo $q$ dòng là các thao tác. Phiên bản $v$ luôn đã tồn tại.

Dữ liệu ra

Với mỗi thao tác loại $2$ in một dòng là đáp án.

Ví dụ

Input

5 5
7 -1 9 -10 9
2 0 1 4
2 0 4 4
1 0 2 951067984
2 1 3 5
1 1 5 443043973

Output

5
-10
8
Giới hạn
  • $1\le n,q\le 10^5$; $|a_i|,|x|\le 10^9$; $1\le l\le r\le n$.
  • Thời gian: 2 giây; bộ nhớ: 256 MB.
Draft saved