verify/yosupo/yosupo_point_add_range_sum_fenwick.test.cpp

• View this file on GitHub
• Last update: 2025-02-27 06:13:46+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• data_structure/fenwick_tree.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <bits/stdc++.h>
using namespace std;

#include "../../data_structure/fenwick_tree.hpp"

int main(){
    int N, Q;
    cin >> N >> Q;

    FenwickTree<long long> bit(N); 

    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        bit.add(i, a);
    }

    for(int i = 0; i < Q; i++) {
        int t;
        cin >> t;
        if(t == 0) {
            int p, x;
            cin >> p >> x;
            bit.add(p, x);
        }

        if(t == 1) {
            int l, r;
            cin >> l >> r;
            cout << bit.sum(l, r) << endl;
        }
    }

    return 0;
}

#line 1 "verify/yosupo/yosupo_point_add_range_sum_fenwick.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <bits/stdc++.h>
using namespace std;

#line 1 "data_structure/fenwick_tree.hpp"
template <typename T=int>
struct FenwickTree {
    int n;
    vector<T> data;
    FenwickTree(int n) : n(n), data(n, 0) {}

    void add(int p, T x) {
        for(p++; p <= n; p += p & -p) data[p - 1] += x;
    }

    T sum(int r) {
        T s = 0;
        for(; r; r -= r & -r) s += data[r - 1];
        return s;
    }
    
    T sum(int l, int r) {
        return sum(r) - sum(l);
    }
};
#line 7 "verify/yosupo/yosupo_point_add_range_sum_fenwick.test.cpp"

int main(){
    int N, Q;
    cin >> N >> Q;

    FenwickTree<long long> bit(N); 

    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        bit.add(i, a);
    }

    for(int i = 0; i < Q; i++) {
        int t;
        cin >> t;
        if(t == 0) {
            int p, x;
            cin >> p >> x;
            bit.add(p, x);
        }

        if(t == 1) {
            int l, r;
            cin >> l >> r;
            cout << bit.sum(l, r) << endl;
        }
    }

    return 0;
}

Back to top page