维护时间复杂度 O(nlogn)
查询时间复杂度 O(logn)
优点:好写
缺点 fw没啥用
主要就是用一个叫lowbit的东西来实现用一个树状的东西维护区间和等,其实只要记住修改的时候+=lowbit(x),查询的时候-=lowbit(x)就行了
1.板子
这个应该都会吧qwq
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int maxn=1e6+5;
int num[maxn];
int c[maxn];
int lowbit(int a){
return(a&-a);
}
int ask(int x){
int res=0;
while(x){
res+=c[x];
x-=lowbit(x);
}
return res;
}
void add(int x,int v){
while(x<=n){
c[x]+=v;
x+=lowbit(x);
}
return;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>num[i];
add(i,num[i]);
}
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
if(a==1){
add(b,c);
}
if(a==2){
cout<<ask(c)-ask(b-1)<<endl;
}
}
return 0;
}
2.区间修改区间查询
这个要用到差分,下面用di表示
转移式 Σ(1,n) ai=Σ(1,n) di(n+1)-dii
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e6 + 5;
int n, m;
int sum[maxn];
int sum2[maxn];
int a[maxn];
int b[maxn];
int lowbit(int x) { return x & -x; }
void add(int x, int v, int t) {
if (t == 1) {
while (x <= n) {
sum[x] += v;
x += lowbit(x);
}
} else {
while (x <= n) {
sum2[x] += v;
x += lowbit(x);
}
}
}
int ask(int x, int t) {
int res = 0;
if (t == 1) {
while (x) {
res += sum[x];
x -= lowbit(x);
}
} else {
while (x) {
res += sum2[x];
x -= lowbit(x);
}
}
return res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int lst = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
add(i, a[i] - lst, 1);
add(i, (i - 1) * (a[i] - lst), 2);
lst = a[i];
}
for (int ii = 1; ii <= m; ii++) {
int co;
cin >> co;
if (co == 1) {
int x, y, k;
cin >> x >> y >> k;
add(x, k, 1);
add(y + 1, -k, 1);
add(x, (x - 1) * k, 2);
add(y + 1, -y * k, 2);
} else {
int x, y;
cin >> x >> y;
cout << ask(y, 1) * y - ask(y, 2) - ask(x - 1, 1) * (x - 1) + ask(x - 1, 2) << endl;
}
}
return 0;
}
3.矩阵修改矩阵查询
转移式 Σ(1,n)Σ(1,m) aij= Σ(1,n)Σ(1,m) ((n+1)(m+1))dij-(m+1)diji-(n+1)dijj+dijij)
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e3+50;
int t[maxn][maxn],ti[maxn][maxn],tj[maxn][maxn],tij[maxn][maxn];
int n,m;
int lowbit(int x){
return x&-x;
}
void add(int x,int y,int k){
int prey=y;
int prex=x;
while(x<=n){
y=prey;
while(y<=m){
t[x][y]+=k;
ti[x][y]+=prex*k;
tj[x][y]+=prey*k;
tij[x][y]+=prex*prey*k;
y+=lowbit(y);
}
x+=lowbit(x);
}
}
int ask(int x,int y){
int prey=y;
int prex=x;
int res=0;
while(x){
y=prey;
while(y){
res+=(prex+1)*(prey+1)*t[x][y]-ti[x][y]*(prey+1)-tj[x][y]*(prex+1)+tij[x][y];
y-=lowbit(y);
}
x-=lowbit(x);
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
int opt;
while(cin>>opt){
int x,y,xx,yy;
cin>>x>>y>>xx>>yy;
if(opt==1){
int k;
cin>>k;
add(x,y,k);
add(x,yy+1,-k);
add(xx+1,y,-k);
add(xx+1,yy+1,k);
}
else{
// cout<<ask(xx,yy)<<" "<<ask(x-1,y-1)<<" "<<ask(xx,y-1)<<" "<<ask(x-1,yy)<<endl;
cout<<ask(xx,yy)+ask(x-1,y-1)-ask(xx,y-1)-ask(x-1,yy)<<endl;
}
}
return 0;
}
完结
标签:树状,int,lowbit,while,long,add,maxn,数组 From: https://www.cnblogs.com/jt0007/p/17502202.html