Query-Sum

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
hhoangcpascal
Dạng bài
Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

  • \(1\) \(p_i\) \(x_i\): Tăng phần tử ở vị trí \(p_i\) lên \(x_i\) đơn vị.
  • \(2\) \(u_i\) \(v_i\): Tính tổng các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu
Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

  • Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
  • Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
  • \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên dương \(p_i\) và \(x_i\) \((1 \leq p_i \leq N\), \(1 \leq x_i \leq 10^4)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

  • Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần atử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

Test 1

Input 
6 5
9 2 4 7 4 8
1 5 6
2 1 5
1 3 8
1 2 3
2 2 4
Output 
32
24

Bình luận


  • -3
    ceaturs    12:25 p.m. 22 Tháng 5, 2024

    dùng fenwick tree cũng được

    #include <bits/stdc++.h>

    using namespace std;

    define ll long long

    define endl "\n"

    define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);

    const int maxN=1e4;
    ll Bittree[maxN+1];

    void update(int idx, ll value){
    while(idx<=maxN){
    Bittree[idx]+=value;
    idx+=idx&-idx;
    }
    }

    ll getN(ll idx){
    ll ans=0;
    while(idx>0){
    ans+=Bittree[idx];
    idx-=idx&-idx;
    }
    return ans;
    }

    ll getLR(ll L, ll R){
    return getN(R)-getN(L-1);
    }

    int main(){
    fastIO
    int n, q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
    ll a;
    cin>>a;
    update(i,a);
    }

    while(q-->0){
ll Ncase, a,b;
cin>>Ncase>>a>>b;
if(Ncase==1){
    update(a,b);
}
else{
    cout<<getLR(a,b)<<endl;
}
}

    return 0;
    }

      • 10 bình luận nữa