首页 > 其他分享 >树状数组3区间查询区间修改

树状数组3区间查询区间修改

时间:2022-10-23 11:01:20浏览次数:40  
标签:前缀 val 树状 int sum long 数组 区间

Description

要求使用树状数组完成区间之和查询,区间加上某一相同数值的操作。

Solution

树状数组是用来单点加,查前缀和的。若要实现区间加,可以将原数列差分,然后在l位置处+val,在r+1处-val,这时要查询的就成了在差分数列上前缀和的前缀和,即二阶前缀和。

\[Sum = \sum_{i=1}^n\sum_{j=1}^i x_j \]

对于第i位来讲,它的值是这样组成的。

\[(i - 0) * x_1 + (i-1)*x_2 + (i-2)*x_2 + \dots + (i - (i - 1)) * x_i \]

化简一下

\[i * \sum_{j=1}^i x_j - \sum_{j=1}^i (j-1) * x_j \]

再化简一下

\[i * \sum_{j=1}^i x_j - \sum_{j=1}^i j * x_j + \sum_{j=1}^i x_j \]

此时就比较明了了,现在就是是要求 \(\sum_{i=1}^n x_i\) 以及 \(\sum_{i=1}^n i*x_i\)这两个前缀和。第二个其实和第一没有什么本质区别,就是在给某一位加上val时,给第二个的前缀和加上i*val

#include<iostream>
using namespace std;
const int N = 1e6+10;
int n;
int A[N];
long long tr1[N] , tr2[N];

inline int lowbit(int x) { return x & (-x); }

inline void Add(int pos , int val)
{
	long long val2 = 1ll * val * pos;
	while(pos <= n) { tr1[pos] += val; tr2[pos] += val2; pos += lowbit(pos); }
}

inline long long Ask1(int pos)
{
	long long Ans = 0;
	while(pos) { Ans += tr1[pos]; pos -= lowbit(pos); }
	return Ans;
}

inline long long Ask2(int pos)
{
	long long Ans = 0;
	while(pos) { Ans += tr2[pos]; pos -= lowbit(pos); }
	return Ans;
}

inline long long Ask(int l , int r)
{
	long long res1 = Ask1(r) * (r + 1) - Ask1(l-1) * l;
	long long res2 = Ask2(r) - Ask2(l-1);
	return res1 - res2;
}

int main()
{
	int Q , op , l , r ,  x;
	cin >> n >> Q;
	for(int i = 1 ; i <= n ; ++i)
		cin >> A[i];
	for(int i = n ; i >= 2 ; --i)
		A[i] = A[i] - A[i-1];
	for(int i = 1 ; i <= n ; ++i)
		Add(i , A[i]);
	while(Q--)
	{
		cin >> op >> l >> r;
		if(op == 1)
		{
			cin >> x;
			Add(l , x); Add(r + 1 , -x);
		}
		else
			cout << Ask(l , r) << '\n';
	}
	return 0;
}

标签:前缀,val,树状,int,sum,long,数组,区间
From: https://www.cnblogs.com/R-Q-R-Q/p/16818111.html

相关文章

  • 实验三 数组、指针与现代c++标准库
    task5#pragmaonce#include<iostream>#include<string>#include<vector>#include<iomanip>usingnamespacestd;classInfo{public:Info(string......
  • R语言广义线性模型索赔频率预测:过度分散、风险暴露数和树状图可视化|附代码数据
    在精算科学和保险费率制定中,考虑到风险敞口可能是一场噩梦。不知何故,简单的结果是因为计算起来更加复杂,只是因为我们必须考虑到暴露是一个异构变量这一事实。保险费率制定中......
  • PHP array_multisort 多维数组排序的理解
    array_multisort(array1,sortingorder,sortingtype,array2,array3...) 1.数组从前往后,依次排序;前一组数中值相同时,才考虑后一个数组中的值排序;2.任一数组排序变......
  • 数组与结构体
    前言先考虑这样的问题:当你被要求定义十个变量时,你会怎么办?可以像a1,a2,a3···这样一个一个的定义出来。但是,当你被要求定义一千个,一万个变量的时候呢?肯定就不能一个一......
  • 数组,指针与现代c++标准
    #include<iostream>#include<algorithm>#include<math.h>#include<string>usingnamespacestd;classInfo{public:Info(stringnickname,stringcon......
  • 后台管理系统 数组去重 避免踩坑!
    不要把数组push放进循环中,后果很严重!!!findIndexfiltersome......
  • 4. 寻找两个正序数组的中位数
    给定两个大小分别为m和n的正序(从小到大)数组 nums1和 nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log(m+n))。示例1:输入:nums1......
  • 数组访问越界
    一、是什么如果定义了一个有n个元素的数组,那么,对这n个元素(下标为0到n-1的元素)的访问都合法,而对这n个元素之外的空间进行访问,就是非法的,称为“越界“。二、如何避免1)检查传......
  • 容器是否能代替数组
    在.net中,很多开发者都喜欢使用List来代替数组进行使用。容器不仅封装了数组几乎所有的基本操作,而且还可以动态扩容,在开发过程中十分的方便。以下的场景更加建议使用数组:容器......
  • 【leetcode_C++_哈希表_day5】242. 有效的字母异位词&&349. 两个数组的交集&&202.快乐
    C++知识补充:(不完全,仅针对本题用的知识点)1.C++类&对象关键字public确定了类成员的访问属性。在类对象作用域内,公共成员在类的外部是可访问的。您也可以指定类的成......