Query-Sum

View as PDF

Points: 1600 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

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\)\(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_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

Comments


  • 0
    ceaturs    12:25 p.m. 22 may, 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;
    }


    • -1
      truongngoclamCB1    12:14 p.m. 28 apr, 2024

      này prefix-sum 🙂


      • 7
        phungminhdung10tin    10:50 a.m. 3 jan, 2024

        to cao phucnguyen0610 chep code


        • 0
          cuzlmnnoxk    12:34 p.m. 28 oct, 2023

          cho mình hỏi là python nó chậm nên ko đc max điểm hay còn thuật toán khác nữa ạ, thấy mí bạn cũng dùng python mà max đc có 10/20 è


          • 1
            datdoo1309    9:23 a.m. 28 sep, 2023
            #include <bits/stdc++.h>
            #define ll long long
            #define endl "\n"
            using namespace std;
            
            // Cấu trúc dữ liệu Segment Tree
            struct SegmentTree 
            {
                int size;
                vector<ll> tree;
            
                SegmentTree(int n) 
                {
                    size = 1;
                    while (size < n) {
                        size *= 2;
                    }
                    tree.assign(2 * size, 0LL);
                }
            
                void update(int i, ll x) 
                {
                    i += size;
                    tree[i] = x;
                    while (i > 1) 
                    {
                        i /= 2;
                        tree[i] = tree[i * 2] + tree[i * 2 + 1];
                    }
                }
            
                ll query(int l, int r) 
                {
                    l += size;
                    r += size;
                    ll sum = 0;
                    while (l <= r) 
                    {
                        if (l % 2 == 1) 
                        {
                            sum += tree[l];
                            l++;
                        }
                        if (r % 2 == 0) 
                        {
                            sum += tree[r];
                            r--;
                        }
                        l /= 2;
                        r /= 2;
                    }
                    return sum;
                }
            };
            
            int main() 
            {
                ios_base::sync_with_stdio(false);
                cin.tie(NULL); cout.tie(NULL);
            
                int n, q; cin >> n >> q;
                vector<ll> a(n);
                SegmentTree st(n);
                for (int i = 0; i < n; i++) 
                {
                    cin >> a[i];
                    st.update(i, a[i]);
                }
            
                while (q--) 
                {
                    int j; cin >> j;
                    if (j == 1) 
                    {
                        int p, x; cin >> p >> x;
                        st.update(p - 1, st.query(p - 1, p - 1) + x);
                    } 
                    else 
                    {
                        int u, v; cin >> u >> v;
                        cout << st.query(u - 1, v - 1) << endl;
                    }
                }
            
                return 0;
            }
            

            ez

            1 reply

            • 0
              penistone    10:27 p.m. 24 sep, 2023

              Bai nay ko duyet binh thuong duoc

              1 reply

              • 3
                dkm    11:40 a.m. 28 jul, 2022

                10^5 mà bạn 10^6 còn cày trâu được nữa mà


                • 2
                  dang7rickroll    4:19 p.m. 12 jan, 2022

                  Bài này trâu vẫn AC 😃 hảo hán đấy


                  • 0
                    VoBaThongL921    9:59 a.m. 24 sep, 2021

                    hmm trâu vẫn ac bài này:)mà ko biết query sum 2 có đc ko:v

                    1 reply

                    • 2
                      ekhoavvdd    10:46 p.m. 28 jan, 2021

                      ơ
                      cầy trâu mà vẫn ac :))
                      lạ ta :)))

                      1 reply