树状数组(区间问题)
本文引自：传送门
目录
一维树状数组
单点更新，区间查询
#include <iostream>
using namespace std;
const int MAX_N=10010;
int C[MAX_N];
int n;
int lowbit(int x){
return x&(-x);
}
int getsum(int x){
int res=0;
for(;x;x-=lowbit(x)){
res+=C[x];
}
return res;
}
void change(int x,int c){
for(;x<=n;x+=x&(-x)){
C[x]+=c;
}
}
int main() {
cin>>n;
for(int i=1;i<=n;i++){
int d;
cin>>d;
change(i,d);
}
for(int i=1;i<=n;i++){
cout<<getsum(i)<<" ";
}
return 0;
}
区间更新，单点查询
原来的值存在a[]里面，多建立个数组c1[],注意：
那么求a[i]的值的时候…..
...
所以就用c1[]建立树状数组，便可以很快查询a[i]的值。
#include<bits/stdc++.h>
#define maxn 1000000
using namespace std;
int a[maxn],c1[maxn],n,m,val,x,y,temp;
inline int lowbit(int x){
return x&-x;
}
void update(int x,int val)
{
while(x<=n)
{
c1[x]+=val;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=0;
while(x)
{
ans+=c1[x];
x-=lowbit(x);
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
update(i,a[i]-a[i-1]);//利用差分构建C数组，只改变两个位置的值
}
while(m--)
{
scanf("%d",&temp);
if(temp==1)
{
scanf("%d",&x);
printf("%d\n",sum(x)); //单点值即为前缀和
}
else
{
scanf("%d%d%d",&x,&y,&val); //将[x,y]区间的值加val
update(x,val);
update(y+1,-val);
}
}
}
区间更新，区间查询
用表示区间
到
的和。
那么...
...
然后我们把式子打开。
…
…
我们可以多建立一个数组c2[]，c2[n]用来存,并且把c2数组也建立成树状数组，那么问题就迎刃而解了。
#include<bits/stdc++.h>
#define maxn 1000000
using namespace std;
int a[maxn],c1[maxn],c2[maxn],n,m,val,x,y,temp;
inline int lowbit(int x){
return x&-x;
}
void update(int *q,int x,int val)
{
while(x<=n)
{
q[x]+=val;
x+=lowbit(x);
}
}
int getsum(int *q,int x)
{
int ans=0;
while(x)
{
ans+=q[x];
x-=lowbit(x);
}
return ans;
}
int sum(int x)
{
int ans1,ans2;
ans1=x*getsum(c1,x);
ans2=getsum(c2,x);
return ans1-ans2;
}
int inquire(int x,int y)
{
int ans1,ans2;
ans1=sum(y);
ans2=sum(x-1);
return ans1-ans2;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
update(c1,i,a[i]-a[i-1]);
update(c2,i,(i-1)*(a[i]-a[i-1]));
}
for(int i=1; i<=m; i++)
{
scanf("%d",&temp);
if(temp==1)
{
scanf("%d%d%d",&x,&y,&val);
update(c1,x,val);
update(c1,y+1,-val);
update(c2,x,(x-1)*val);
update(c2,y+1,-y*val);
}
else
{
scanf("%d%d",&x,&y);
printf("%d\n",inquire(x,y));
}
}
}
/*
5 2
1 4 10 7 8
1
2 4 -2
2
1 3
*/
二维树状数组
单点更新，区间查询
1.对矩阵的某个数进行修改，
2.查询某个子矩阵的所有元素的和
#include <iostream>
using namespace std;
const int MAX_N=810;
int C[MAX_N][MAX_N];
int n;
int lowbit(int x){
return x&(-x);
}
void change(int i,int j,int delta){
for(int x=i;x<=n;x+=lowbit(x)){
for(int y=j;y<=n;y+=lowbit(y)){
C[x][y]+=delta;
}
}
}
int getsum(int i,int j){
int res=0;
for(int x=i;x;x-=lowbit(x)){
for(int y=j;y;y-=lowbit(y)){
res+=C[x][y];
}
}
return res;
}
int main() {
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int d;
cin>>d;
change(i,j,d);
}
}
int x,y;
cin>>x>>y;
cout<<getsum(x,y)<<endl;
return 0;
}
区间更新，单点查询
二维前缀和：
那么我们可以令差分数组表示
与
的差。
例如下面这个矩阵
1 4 8
6 7 2
3 9 5
对应的差分数组就是
1 3 4
5 -2 -9
-3 5 1
当我们想要将一个矩阵加上x时，怎么做呢？
下面是给最中间的3*3矩阵加上x时，差分数组的变化：
0 0 0 0 0
0 +x 0 0 -x
0 0 0 0 0
0 0 0 0 0
0 -x 0 0 +x
0 0 0 0 0
0 x x x 0
0 x x x 0
0 x x x 0
0 0 0 0 0
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e3+10;
int C[MAX_N][MAX_N];
int a[MAX_N][MAX_N];
int n,m;
int lowbit(int x){
return x&(-x);
}
void change(int i,int j,int delta){
for(int x=i;x<=n;x+=lowbit(x)){
for(int y=j;y<=m;y+=lowbit(y)){
C[x][y]+=delta;
}
}
}
void range_change(int xa,int ya,int xb,int yb,int w){
change(xa,ya,w);
change(xa,yb+1,-w);
change(xb+1,ya,-w);
change(xb+1,yb+1,w);
}
int getsum(int i,int j){
int res=0;
for(int x=i;x;x-=lowbit(x)){
for(int y=j;y;y-=lowbit(y)){
res+=C[x][y];
}
}
return res;
}
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
change(i,j,a[i][j]-(a[i-1][j]+a[i][j-1]-a[i-1][j-1]));
}
}
int q,tmp;
cin>>q;
while(q--){
cin>>tmp;
if(tmp){ //修改
int x1,x2,y1,y2,w;
cin>>x1>>y1>>x2>>y2>>w;
range_change(x1,y1,x2,y2,w);
}else{ //查询
int x,y;
cin>>x>>y;
cout<<getsum(x,y)<<endl;
}
}
return 0;
}
/*
3 3
1 4 8
6 7 2
3 9 5
2
1
1 1 3 3 2
0
2 3
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e3+10;
int a[MAX_N][MAX_N];
int n,m;
int C1[MAX_N][MAX_N],C2[MAX_N][MAX_N],C3[MAX_N][MAX_N],C4[MAX_N][MAX_N];
int lowbit(int x){
return x&(-x);
}
void change(int i,int j,int w){
for(int x=i;x<=n;x+=lowbit(x)){
for(int y=j;y<=m;y+=lowbit(y)){
C1[x][y]+=w;
C2[x][y]+=w*i;
C3[x][y]+=w*j;
C4[x][y]+=w*i*j;
}
}
}
void range_change(int xa,int ya,int xb,int yb,int w){
change(xa,ya,w);
change(xa,yb+1,-w);
change(xb+1,ya,-w);
change(xb+1,yb+1,w);
}
int getsum(int i,int j){
int res=0;
for(int x=i;x;x-=lowbit(x)){
for(int y=j;y;y-=lowbit(y)){
res+=(i+1)*(j+1)*C1[x][y]
-(j+1)*C2[x][y]
-(i+1)*C3[x][y]
+C4[x][y];
}
}
return res;
}
int range_sum(int xa,int ya,int xb,int yb){
return getsum(xb,yb)-getsum(xb,ya-1)-getsum(xa-1,yb)+getsum(xa-1,ya-1);
}
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
change(i,j,a[i][j]-(a[i-1][j]+a[i][j-1]-a[i-1][j-1]));
}
}
int q,tmp;
cin>>q;
while(q--){
cin>>tmp;
if(tmp){ //修改
int x1,x2,y1,y2,w;
cin>>x1>>y1>>x2>>y2>>w;
range_change(x1,y1,x2,y2,w);
}else{ //查询
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
cout<<range_sum(x1,y1,x2,y2)<<endl;
}
}
return 0;
}
/*
3 3
1 4 8
6 7 2
3 9 5
2
1
1 1 3 3 -4
0
2 2 3 3
*/
区间最值
只支持末端插入不支持单点修改操作。
#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e3+5;
int C[MAX_N];
int a[MAX_N];
int lowbit(int x){
return x&(-x);
}
void change(int r) {
C[r] = a[r];
for(int i = 1; i < lowbit(r); i <<= 1)
C[r] = max(C[r], C[r-i]);
}
int getmax(int l, int r) {
int ret = a[r];
while(l <= r) {
ret = max(ret, a[r]);
for(--r; r - l >= lowbit(r); r -= lowbit(r))
ret = max(ret, C[r]);
}
return ret;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
change(i);
}
int q;
scanf("%d",&q);
while(q--){
int l;int r;
scanf("%d%d",&l,&r);
printf("%d\n",getmax(l,r));
}
}
}