【单点修改，区间查询】洛谷 P3374 【模板】树状数组 1

题目

https://www.luogu.com.cn/problem/P3374

参考代码

#include<bits/stdc++.h>
typedef long long ll;template<typename E, typename F, typename F_INVERSE>
class FenwickTree {// 树状数组
private:std::vector<E> raw;// 维护原数据std::vector<E> tree;// 树状数组int arr_size;// 元素个数F func;// 代表元素运算规则，例如加法F_INVERSE func_inverse;// 代表 func 的逆运算规则，例如加法的逆运算规则就是减法E defaultValue;// 树状数组初始化的元素值bool prefixToSuffix;// 用前缀树状数组维护后缀树状数组/* 计算出 x 二进制形式下最低位的 1 */inline int lowbit(int x) {return x & -x;}/* 有可能使用前缀树状数组维护后缀树状数组，因此需要计算出真实下标位置 */inline int calculateRealIndex(int x) {return prefixToSuffix ? arr_size - x + 1 : x;}public:/*** 容器内的元素下标从 0 开始存放，但是树状数组的使用是从下标 1 开始使用* @tparam Container 容器类型* @param arr 存放元素的容器* @param arr_size 容器大小* @param func 容器中元素的运算规则* @param func_inverse 容器中元素的逆运算规则* @param defaultValue 容器中元素的默认值*/template<typename Container>FenwickTree(Container&& arr, int arr_size, F func, F_INVERSE func_inverse, E defaultValue, bool prefixToSuffix = false): arr_size(arr_size), func(func), func_inverse(func_inverse), defaultValue(defaultValue), prefixToSuffix(prefixToSuffix) {raw.resize(arr_size + 1);tree.assign(arr_size + 1, defaultValue);for (int i = 0; i < arr_size; ++ i) {raw[i + 1] = arr[i];pointUpdate(i + 1, arr[i]);}}/* 没有初始容器数据的构造器 */FenwickTree(int arr_size, F func, F_INVERSE func_inverse, E defaultValue, bool prefixToSuffix = false): arr_size(arr_size), func(func), func_inverse(func_inverse), defaultValue(defaultValue), prefixToSuffix(prefixToSuffix) {raw.assign(arr_size + 1, defaultValue);tree.assign(arr_size + 1, defaultValue);}/* 单点赋值：将下标 index（从 1 开始）的值改为 newValue */void pointAssign(int index, E newValue) {// 原本的值为 value 要变为 newValue，相当于 func(value, func_inverse(newValue, value))index = calculateRealIndex(index);E delta = func_inverse(newValue, raw[index]);raw[index] = newValue;pointUpdate(index, delta);}/* 单点修改：将下标 index（从 1 开始）的值与 value 进行 func 运算 */void pointUpdate(int index, E value) {index = calculateRealIndex(index);for (int i = index; i <= arr_size; i += lowbit(i)) {tree[i] = func(tree[i], value);}}/* 前缀查询：查询下标 index（从 1 开始）的值 */E prefixQuery(int index) {index = calculateRealIndex(index);E res = defaultValue;for (int i = index; i > 0; i -= lowbit(i)) {res = func(res, tree[i]);}return res;}/* 区间查询：查询区间 [leftIndex, rightIndex] 进行 func 运算的结果 */E rangeQuery(int leftIndex, int rightIndex) {E difference = func_inverse(prefixQuery(rightIndex), prefixQuery(leftIndex - 1));// 使用 func 的逆运算规则 func_inverse 做差分return difference;// 差分的值即为区间 [leftIndex, rightIndex] 进行 func 运算的结果}
};class FenwickTreeFactory {
public:/* 前缀模式的加法树状数组：修改向后，查询向前 */template<typename Container>static auto add(Container&& arr, int arrSize, bool prefixToSuffix = false) {using T = std::remove_reference_t<decltype(arr[0])>;auto add_func = [](T a, T b) { return a + b; };auto sub_func = [](T a, T b) { return a - b; };return FenwickTree<T, decltype(add_func), decltype(sub_func)>(std::forward<Container>(arr), arrSize, add_func, sub_func, T(0), prefixToSuffix);}/* 后缀模式的加法树状数组：修改向前，查询向后 */template<typename Container>static auto addSuffix(Container&& arr, int arrSize) {return add(arr, arrSize, true);}// 乘法树状数组template<typename Container>static auto mul(Container&& arr, int arrSize) {using T = std::decay_t<decltype(arr[0])>;return FenwickTree<T,decltype([](T a, T b) { return a * b; }),decltype([](T a, T b) { return a / b; })>(std::forward<Container>(arr), arrSize,[](T a, T b) { return a * b; },[](T a, T b) { return a / b; },T(1));}// 异或树状数组template<typename Container>static auto xors(Container&& arr, int arrSize) {using T = std::decay_t<decltype(arr[0])>;auto op = [](T a, T b) { return a ^ b; };return FenwickTree<T, decltype(op), decltype(op)>(std::forward<Container>(arr), arrSize, op, op, T(0));}// 模加法树状数组template<typename Container>static auto modAdd(Container&& arr, int arrSize,std::decay_t<decltype(arr[0])> mod) {using T = std::decay_t<decltype(arr[0])>;auto add = [mod](T a, T b) { return (a + b) % mod; };auto sub = [mod](T a, T b) { return (a - b + mod) % mod; };return FenwickTree<T, decltype(add), decltype(sub)>(std::forward<Container>(arr), arrSize, add, sub, T(0));}// 通用自定义工厂template<typename Container, typename Func, typename InvFunc>static auto custom(Container&& arr, int arrSize,Func func, InvFunc invFunc,std::decay_t<decltype(arr[0])> defaultVal) {using T = std::decay_t<decltype(arr[0])>;return FenwickTree<T, Func, InvFunc>(std::forward<Container>(arr), arrSize, func, invFunc, defaultVal);}
};constexpr int N = 5e5 + 7;
int a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#ifdef ACM_LOCALfreopen("testCase.in", "r", stdin);freopen("testCase.out", "w", stdout);
#endifint n, m, op, x, y;std::cin >> n >> m;for (int i = 0; i < n; ++i) std::cin >> a[i];auto tr = FenwickTreeFactory::add(a, n);while (m --) {std::cin >> op >> x >> y;if (op == 1) {tr.pointUpdate(x, y);} else {std::cout << tr.rangeQuery(x, y) << '\n';}}return 0;
}