DataStructure/test/fenwick_pointaddrangesum.test.cpp

View this file on GitHub
Last update: 2023-01-07 01:54:04+08:00
Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

Code

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

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

#include "../Fenwick/Fenwick.h"
#include "../../buffered_reader.h"

#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n = IO::get<int>();
    int q = IO::get<int>();

    Fenwick<long long> f(n);
    REP(i,n) {
        int x = IO::get<int>();
        f.update(i, x);
    }

    while (q--) {
        int typ = IO::get<int>();
        if (typ == 0) {
            int u = IO::get<int>();
            int val = IO::get<int>();
            f.update(u, val);
        } else if (typ == 1) {
            int l = IO::get<int>();
            int r = IO::get<int>();
            cout << f.get(l, r) << '\n';
        } else {
            assert(false);
        }
    }
    return 0;
}

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

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

#line 1 "DataStructure/Fenwick/Fenwick.h"
// 1D Fenwick {{{
// 0 based index
//
// Tested:
// - https://judge.yosupo.jp/problem/static_range_sum
// - https://judge.yosupo.jp/problem/point_add_range_sum
template<
    typename T  // need to support operators + -
> struct Fenwick {
    Fenwick(int _n) : n(_n), f(_n + 1) {}

    // a[u] += val
    void update(int u, T val) {
        assert(0 <= u && u < n);
        ++u;
        for (; u <= n; u += u & -u) {
            f[u] += val;
        }
    }

    // return a[0] + .. + a[u-1]
    T get(int u) const {
        assert(0 <= u && u <= n);
        T res = 0;
        for (; u > 0; u -= u & -u) {
            res += f[u];
        }
        return res;
    }

    // return a[l] + .. + a[r-1]
    T get(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return 0;  // empty
        return get(r) - get(l);
    }

    void reset() {
        std::fill(f.begin(), f.end(), T(0));
    }

    int n;
    vector<T> f;
};
// }}}
#line 1 "buffered_reader.h"
// Buffered reader {{{
namespace IO {
    const int BUFSIZE = 1<<14;
    char buf[BUFSIZE + 1], *inp = buf;

    bool reacheof;
    char get_char() {
        if (!*inp && !reacheof) {
            memset(buf, 0, sizeof buf);
            int tmp = fread(buf, 1, BUFSIZE, stdin);
            if (tmp != BUFSIZE) reacheof = true;
            inp = buf;
        }
        return *inp++;
    }
    template<typename T>
    T get() {
        int neg = 0;
        T res = 0;
        char c = get_char();
        while (!std::isdigit(c) && c != '-' && c != '+') c = get_char();
        if (c == '+') { neg = 0; }
        else if (c == '-') { neg = 1; }
        else res = c - '0';

        c = get_char();
        while (std::isdigit(c)) {
            res = res * 10 + (c - '0');
            c = get_char();
        }
        return neg ? -res : res;
    }
};
// Helper methods
int ri() {
    return IO::get<int>();
}
// }}}
#line 8 "DataStructure/test/fenwick_pointaddrangesum.test.cpp"

#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n = IO::get<int>();
    int q = IO::get<int>();

    Fenwick<long long> f(n);
    REP(i,n) {
        int x = IO::get<int>();
        f.update(i, x);
    }

    while (q--) {
        int typ = IO::get<int>();
        if (typ == 0) {
            int u = IO::get<int>();
            int val = IO::get<int>();
            f.update(u, val);
        } else if (typ == 1) {
            int l = IO::get<int>();
            int r = IO::get<int>();
            cout << f.get(l, r) << '\n';
        } else {
            assert(false);
        }
    }
    return 0;
}