Cập Nhật Đoạn, Truy Vấn Điểm

Cho mảng $a$ gồm $n$ số nguyên (đánh số từ $0$). Ban đầu mảng được khởi tạo bằng $0$. Cài đặt cấu trúc dữ liệu hỗ trợ hai thao tác:

• Cập nhật đoạn: thêm $v$ vào tất cả các phần tử $a[l],a[l+1],\dots ,a[r]$.
• Truy vấn điểm: trả về giá trị $a[i]$ hiện tại.

Hàm cần cài đặt

Đây là bài toán signature grader. Bạn chỉ cần cài đặt ba hàm sau, không cần viết main() hay đọc/ghi dữ liệu.

Ngôn ngữ hỗ trợ: C/C++, Python, và Java.

C++

void init(int n);
void update(int l, int r, long long v);
long long query(int i);

Python

def init(n: int) -> None: ...
def update(l: int, r: int, v: int) -> None: ...
def query(i: int) -> int: ...

Java

public class Solution {
    public void init(int n) { ... }
    public void update(int l, int r, long v) { ... }
    public long query(int i) { ... }
}

Mô tả

• init(n): Khởi tạo cấu trúc với $n$ phần tử, tất cả bằng $0$.
• update(l, r, v): Cộng $v$ vào $a[l],a[l+1],\dots ,a[r]$.
• query(i): Trả về giá trị hiện tại của $a[i]$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• Tổng số thao tác $update$ và $query$: $\le 2·{10}^5$
• $0\le l\le r<n$
• $|v|\le {10}^9$

Ví dụ