verify/verify-yosupo-ds/yosupo-fenwick.test.cpp

• View this file on GitHub
• Last update: 2025-03-29 17:57:48+08:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• src/alfred/config/io-sync-off.hpp
• src/alfred/data_structure/fenwick.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum

#include "../../src/alfred/config/io-sync-off.hpp"
#include "../../src/alfred/data_structure/fenwick.hpp"
#include <iostream>

int main(int argc, char const *argv[]) {
    int n, q, opt, x, v;
    optimizeIO(), std::cin >> n >> q;

    Fenwick<long long> C(n);
    for (int i = 0; i < n; i++) {
        std::cin >> x, C.update(i, x);
    }

    while (q--) {
        std::cin >> opt >> x >> v;
        if (opt == 0) {
            C.update(x, v);
        } else {
            std::cout << C.query(x, v - 1) << '\n';
        }
    }

    return 0;
}

#line 1 "verify/verify-yosupo-ds/yosupo-fenwick.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum

#line 1 "src/alfred/config/io-sync-off.hpp"
#include <bits/stdc++.h>

inline void optimizeIO(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
}
#line 1 "src/alfred/data_structure/fenwick.hpp"



#line 5 "src/alfred/data_structure/fenwick.hpp"

template <class T>
struct Fenwick {
    std::vector<T> c;
    inline int lowbit(int x) { return x & -x; }
    inline void merge(T &x, T &y) { x = x + y; }
    inline T subtract(T x, T y) { return x - y; }
    inline void update(size_t pos, T x) {
        for (pos++; pos < c.size(); pos += lowbit(pos)) merge(c[pos], x);
    }
    inline void clear(void) {
        for (auto &x : c) x = T();
    }
    inline T query(size_t pos) {
        T ans = T();
        for (pos++; pos; pos ^= lowbit(pos)) merge(ans, c[pos]);
        return ans;
    }
    inline T query(size_t l, size_t r) {
        return l == 0 ? query(r) : subtract(query(r), query(l - 1));
    }
    inline int kth(const T k) {
        int ans = 0;
        for (int i = 1 << std::__lg(c.size() - 1); i; i >>= 1) {
            if (ans + i < (int)c.size() && c[ans + i] <= k) {
                k -= c[ans + i], ans += i;
            }
        }
        return ans;
    }
    Fenwick(size_t len) : c(len + 2) {}
};


#line 6 "verify/verify-yosupo-ds/yosupo-fenwick.test.cpp"

int main(int argc, char const *argv[]) {
    int n, q, opt, x, v;
    optimizeIO(), std::cin >> n >> q;

    Fenwick<long long> C(n);
    for (int i = 0; i < n; i++) {
        std::cin >> x, C.update(i, x);
    }

    while (q--) {
        std::cin >> opt >> x >> v;
        if (opt == 0) {
            C.update(x, v);
        } else {
            std::cout << C.query(x, v - 1) << '\n';
        }
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	150 ms	7 MB
g++	max_random_01	AC	151 ms	7 MB
g++	max_random_02	AC	155 ms	7 MB
g++	max_random_03	AC	155 ms	7 MB
g++	max_random_04	AC	153 ms	7 MB
g++	random_00	AC	130 ms	6 MB
g++	random_01	AC	130 ms	7 MB
g++	random_02	AC	91 ms	4 MB
g++	random_03	AC	43 ms	7 MB
g++	random_04	AC	47 ms	5 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	5 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	5 ms	4 MB
g++	small_05	AC	5 ms	4 MB
g++	small_06	AC	5 ms	4 MB
g++	small_07	AC	5 ms	4 MB
g++	small_08	AC	5 ms	4 MB
g++	small_09	AC	5 ms	4 MB

Back to top page