Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Truy vấn tổng cây con với Euler tour

    Cho cây gốc tại đỉnh 111 gồm nnn đỉnh, đỉnh iii có giá trị aia_iai​. Xử lý qqq truy vấn:

    • 1 x y: gán ax=ya_x = yax​=y (cập nhật điểm).
    • 2 x: in tổng giá trị tất cả đỉnh trong cây con gốc xxx (bao gồm xxx).

    Dùng Euler tour kết hợp Fenwick để đạt O(log⁡n)O(\log n)O(logn) mỗi truy vấn.

    • Định dạng đầu vào:

      Dòng đầu: nnn, qqq. Dòng hai: nnn giá trị a1…ana_1\dots a_na1​…an​. n−1n-1n−1 dòng: các cạnh uuu, vvv. qqq dòng truy vấn như mô tả.

    • Ràng buộc đầu vào:

      1≤n,q≤2⋅1051 \le n,q \le 2\cdot10^51≤n,q≤2⋅105, ∣ai∣,∣y∣≤109|a_i|,|y| \le 10^9∣ai​∣,∣y∣≤109.

    • Định dạng đầu ra:

      Với mỗi truy vấn loại 2, in tổng cây con trên một dòng.

    Ví dụ:

    Đầu vào:

    5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
2 2
1 4 10
2 1

    Đầu ra:

    11
21

    Giải thích:

    Cây con của 2 gồm {2,4,5}=2+4+5=11. Sau khi a4=10, cây con của 1 (cả 5 đỉnh) = 1+2+3+10+5=21.

    Đang tải editor...