Query-Sum

Tác giả:

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

ronaldo12345 • 10:32 a.m. 14 Tháng 1, 2025 • ← chỉnh sửa 3 →

nope

-2
Phản hồi Chia sẻ

HH_lethethanhlong_2009 • 8:27 a.m. 17 Tháng 10, 2024 •

cho e hỏi bài này dùng prefix sum kiểu gì vậy ạ? hay phải dùng tree

-1
Phản hồi Chia sẻ

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;
}
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
-5
Phản hồi Chia sẻ

truongngoclamCB1 • 12:14 p.m. 28 Tháng 4, 2024 •

này prefix-sum 🙂

-2
Phản hồi Chia sẻ

phungminhdung10tin • 10:50 a.m. 3 Tháng 1, 2024 •

to cao phucnguyen0610 chep code

7
Phản hồi Chia sẻ

cuzlmnnoxk • 12:34 p.m. 28 Tháng 10, 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 è

0
Phản hồi Chia sẻ

#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;
}

Phản hồi

1 phản hồi