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

    solution

    Đề bài: [Giải thuật] Cây chỉ số nhị phân Fenwick tổng đoạn

    Cho mảng a1,…,ana_1,\dots,a_na1​,…,an​ (chỉ số từ 111). Xử lý qqq truy vấn:

    • 1 p x: gán ap=xa_p = xap​=x.
    • 2 l r: in tổng al+al+1+⋯+ara_l + a_{l+1} + \dots + a_ral​+al+1​+⋯+ar​.

    Hãy dùng cây chỉ số nhị phân (Fenwick / BIT).

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

      Dòng đầu: nnn, qqq. Dòng hai: nnn phần tử. qqq dòng truy vấn.

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

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

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

      Mỗi truy vấn loại 2 in tổng đoạn trên một dòng.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    15
16

    Giải thích:

    Tổng cả mảng = 15. Gán a3=10. Tổng a2..a4 = 2+10+4 = 16.

    Đang tải editor...