首页 > 其他分享 >二维树状数组

二维树状数组

时间:2024-11-07 14:32:07浏览次数:1  
标签:树状 int sum 修改 二维 数组 区间

前置知识

树状数组(不会就学一下再来)

简介

因为树状数组可以非常简洁解决序列上的一些问题,所以考虑能否用树状数组解决矩阵(二维序列)的问题。
比较暴力的想法是对于每一横行建一个树状数组,再对每一列建一个树状数组统计答案。
但这样显然要\(n+m\)个树状数组,但是我们发现这些树状数组复用了一些节点,所以我们考虑不用真的建出横行的树状数组,直接用竖行的就可以储存所有信息。

用法

单点修改 区间查询

树状数组直接记和,查询就是二维区间和的式子,单点修改就是直接改,考虑会对哪些树状数组的点进行修改即可。

void add(int x,int y,int d)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))
            sh[i][j]+=d;
}
LL query(int x,int y)
{
    LL ret=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
            ret+=sh[i][j];
    return ret;
}

区间修改 单点查询

区间修改就不能直接记和,记差分(二维差分为\(d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]\),你会发现性质与一维差分相同)。
考虑一次修改会对差分数组带来什么影响。(对黄色区间区间加\(w\),差分数组四个红色点要修改)
image

所以\(a[i][j]=\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]\)。
树状数组代码与上面相同,主函数改一下修改即可

区间修改 区间查询

结合上两个即可。
区间修改用差分,但区间求和怎么办?

\[sum[i][j]=\sum_{i=1}^{x}\sum_{j=1}^{y}\sum_{h=1}^{i}\sum_{k=1}^{j}d[h][k] \]

\[sum[i][j]=\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j](x-i+1)(y-j+1) \]

\[sum[i][j]=\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]ij+d[i][j](xy+x+y+1)-d[i][j]i(y+1)-d[i][j]j(x+1) \]

所以维护4个二维树状数组,分别存\(d[i][j]\),\(d[i][j]ij\),\(d[i][j]i\),\(d[i][j]j\)即可。

inline void modify(int id,int x,int y,int w)
{
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=m;j+=lowbit(j))
			sh[id][i][j]+=w;
}
inline int query(int id,int x,int y)
{
	int ans=0;
	for(int i=x;i;i-=lowbit(i))
		for(int j=y;j;j-=lowbit(j))
			ans+=sh[id][i][j];
	return ans;
}
inline void modifyz(int a,int b,int zhi)
{
	modify(0,a,b,zhi);modify(1,a,b,zhi*a*b);modify(2,a,b,zhi*a);modify(3,a,b,zhi*b);
}
inline int sum(int a,int b)
{
	return query(0,a,b)*(a*b+a+b+1)+query(1,a,b)-query(2,a,b)*(b+1)-query(3,a,b)*(a+1);
}

例题

P4514 上帝造题的七分钟

板子题,实现上面的区间修改区间查询即可。(注意自己认真推一下修改和查询的位置,不要写错了)

#include <bits/stdc++.h>
using namespace std;
const int N=2050;
int n,m,sh[4][N][N];
char s;
int lowbit(int x){return x&(-x);}
inline void modify(int id,int x,int y,int w)
{
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=m;j+=lowbit(j))
			sh[id][i][j]+=w;
}
inline int query(int id,int x,int y)
{
	int ans=0;
	for(int i=x;i;i-=lowbit(i))
		for(int j=y;j;j-=lowbit(j))
			ans+=sh[id][i][j];
	return ans;
}
inline void modifyz(int a,int b,int zhi)
{
	modify(0,a,b,zhi);modify(1,a,b,zhi*a*b);modify(2,a,b,zhi*a);modify(3,a,b,zhi*b);
}
inline int sum(int a,int b)
{
	return query(0,a,b)*(a*b+a+b+1)+query(1,a,b)-query(2,a,b)*(b+1)-query(3,a,b)*(a+1);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>s>>n>>m;
	int a,b,c,d,zhi;
	while(cin>>s>>a>>b>>c>>d)
	{
		if(s=='L')
		{
			cin>>zhi;
			modifyz(a,b,zhi);modifyz(c+1,b,-zhi);modifyz(c+1,d+1,zhi);modifyz(a,d+1,-zhi); 
		}
		else
		{
			int ans;
			ans=sum(c,d)-sum(c,b-1)-sum(a-1,d)+sum(a-1,b-1);
			cout<<ans<<'\n'; 
		}
	}
	return 0;
}

Iahub and Xors

类似于与上面的区间修改,区间查询,但是这里不是加,而是异或。
把所有加减和乘变成异或即可。因为\(x \oplus x=0\),最后那个式子不关心具体的数值,只关心奇偶性,只有同奇偶才有贡献,所以多开两维记一下x,y奇偶性,只在奇偶性相同的之间统计答案即可。(也可以仿照上一个题一样写)

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
#define int long long
int n,m,sh[2][2][N][N];
int lowbit(int x){return x&(-x);}
int query(int x,int y)
{
	int res=0;
	for(int i=x;i>0;i-=lowbit(i))
		for(int j=y;j>0;j-=lowbit(j))
			res^=sh[x%2][y%2][i][j];
	return res;
}
void modify(int x,int y,int w)
{
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=n;j+=lowbit(j))
			sh[x%2][y%2][i][j]^=w;
	return ;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int opt,xx1,xx2,yy1,yy2,w;
		cin>>opt>>xx1>>yy1>>xx2>>yy2;
		if(opt==1)
		{
			int ans1=query(xx2,yy2)^query(xx1-1,yy2)^query(xx1-1,yy1-1)^query(xx2,yy1-1);
			cout<<ans1<<'\n';
		}	
		else
		{
			cin>>w;
			modify(xx1,yy1,w);
			modify(xx2+1,yy1,w);
			modify(xx1,yy2+1,w);
			modify(xx2+1,yy2+1,w);
		}
	}
	return 0;
} 

标签:树状,int,sum,修改,二维,数组,区间
From: https://www.cnblogs.com/storms11/p/18531893

相关文章

  • CUDA开始的GPU编程 - 第四章:C++封装GPU上的数组
    第四章:C++封装GPU上的数组std::vector的秘密:第二模板参数**你知道吗?**std::vector作为模板类,其实有两个模板参数:std::vector<T,AllocatorT>那为什么我们平时只用了std::vector呢?因为第二个参数默认是std::allocator。也就是std::vector等价于std::vector<T,s......
  • 华为OD机试真题-数组二叉树码-2024年OD统一考试(E卷)
    最新华为OD机试考点合集:华为OD机试2024年真题题库(E卷+D卷+C卷)_华为od机试题库-CSDN博客     每一题都含有详细的解题思路和代码注释,精编c++、JAVA、Python三种语言解法。帮助每一位考生轻松、高效刷题。订阅后永久可看,发现新题及时跟新。题目描述二叉树也可以用数组来......
  • LeetCode3264[K次乘运算后的最终数组I]
    题目链接LeetCode3264[K次乘运算后的最终数组I]详情实例实例1实例2提示题解思路先找到最小值然后对最小值进行操作最后输出容器代码classSolution{public:intfindVecMinNumIndex(vector<int>nums)//找出最小值的下标{inti=0,iMin......
  • lanqiaoOJ 1110:小王子单链表 ← 数组模拟实现
     【题目来源】https://www.lanqiao.cn/problems/1110/learning/【题目描述】小王子有一天迷上了排队的游戏,桌子上有标号为1-10的10个玩具,现在小王子将他们排成一列,可小王子还是太小了,他不确定他到底想把哪个玩具摆在哪里,直到最后才能排成一条直线,求玩具的编号。已知他排......
  • 数组的介绍--Java
    1、数组是什么    数组就是一个容器,里面存放的是一组同种类型的数据。    Example:    1,3,5,7,8,10,12    int[]arr={1,3,5,7,8,10,12};    //  该数组存放的都是整型数据    李白,后羿,诸葛亮,刘邦,庄周    ......
  • 7-5 一维数组按规律输出。
    分数10作者苑丽红单位长春理工大学从键盘输入n个整数,将这n个整数按给定的规律输出。建议一维数组实现。输入格式:先输入n的值。再另起一行输入n个元素,空格分隔。输出格式:输出n行数据。数据的规律见输出样例。(共n行。第i行,从所给定数据的第i个开始,顺序输出给定的所......
  • Java中数组“扩容”
    数组一旦创建是不能改变大小的!!!!!此处的数组"扩容"是看起来的像扩容的一种使用方式而已,不是真的改变数组大小.....可以实现,让数组用的时候感觉变大了....思路:其实创建了一个更大的数组,然后将之前数组元素拷贝大数组中,然后将大数组返回给你用。publicstaticvoidmai......
  • Python——数据结构与算法-时间复杂度&空间复杂度-链表&树状结构
    1.数据结构和算法简介程序可以理解为:程序=数据结构+算法概述/目的:都可以提高程序的效率(性能)数据结构指的是存储,组织数据的方式.算法指的是为了解决实际业务问题而思考思路和方法,就叫:算法.2.算法的5大特性介绍概述:为了解决实际业务问题,......
  • 数据处理与统计分析——01-Numpy的属性&ndarray数组创建
    Numpy的属性Numpy简介NumPy(NumericalPython)是Python数据分析必不可少的第三方库NumPy的出现一定程度上解决了Python运算性能不佳的问题,同时提供了更加精确的数据类型,使其具备了构造复杂数据类型的能力。本身是由C语言开发,是个很基础的扩展,NumPy被Python其它科学计算包作......
  • 学习java的第三天,循环语句(for-while-do while),数组,随机数
    for循环for循环是我最喜欢使用的循环语句,清晰,简洁。##for循环的格式为:for(初始化值,如inti=0;循环条件,如i<10;重新赋值,如i++){ 代码块}注:1.初始化值必须为表达式,如i=0"for(i=0;i<3;i++)"或for(inti=0;i<3;i++),但不可以是一个单独的变量如for(i;i<3;i++)这样会报错!......