树状数组基础操作总结
程序员文章站
2022-05-22 08:23:18
...
树状数组用于对区间修改和查询频繁的题
树状数组基础操作
1.单点修改+区间查询
转载大佬的说法
模板题
模板代码
#include <bits/stdc++.h>
inline int read(){char c = getchar();int x = 0,s = 1;
while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
return x*s;}
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x)&(-x)
const int N = 5e5 + 10;
const long long INFINF = 0x7f7f7f7f7f7f7f;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const unsigned long long mod = 998244353;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
int arr[N];
void update(int x,int num,int n)
{
for(int i = x;i <= n;i += lowbit(i))
arr[i] += num;
}
int getsum(int x)
{
int ans = 0;
for(int i = x;i;i -= lowbit(i))
ans += arr[i];
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,m;
cin >> n >> m;
for(int i = 1,num;i <= n;i++)
{
cin >> num;
update(i,num,n);
}
while(m--)
{
int a,b,c;
cin >> a >> b >> c;
if(a == 1)
update(b,c,n);
else
cout << getsum(c)-getsum(b-1) << endl;
}
}
2.区间修改+单点查询
转载大佬的说法
模板题
利用差分思想
模板代码
#include <bits/stdc++.h>
inline int read(){char c = getchar();int x = 0,s = 1;
while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
return x*s;}
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x)&(-x)
const int N = 5e5 + 10;
const long long INFINF = 0x7f7f7f7f7f7f7f;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const unsigned long long mod = 998244353;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
int arr[N],n,m;
void update(int x,int y)
{
while(x <= n)
{
arr[x] += y;
x += lowbit(x);
}
}
ll getsum(int x)
{
ll ans = 0;
while(x <= n)
{
ans += arr[x];
x += lowbit(x);
}
return ans;
}
ll query(int x)
{
ll ans = 0;
while(x)
{
ans += arr[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> m;
ll last = 0,now;
for(int i = 1;i <= n;i++)
{
cin >> now;
update(i,now-last);
last = now;
}
while(m--)
{
int a;
cin >> a;
if(a == 1)
{
int x,y,k;
cin >> x >> y >> k;
update(x,k);
update(y+1,-k);
}
else
{
int x;
cin >> x;
cout << query(x) << endl;
}
}
}
3.区间修改+区间查询
转载大佬的说法
基于区间修改+单点查询中的差分思想,再结合公式推导得出
模板题
模板代码
#include <bits/stdc++.h>
inline long long read(){char c = getchar();long long x = 0,s = 1;
while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
return x*s;}
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x)&(-x)
const int N = 5e5 + 10;
const long long INFINF = 0x7f7f7f7f7f7f7f;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const unsigned long long mod = 998244353;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
ll sum1[N],sum2[N],n,m,last;
void update(ll x,ll y)
{
for(ll i = x;i <= n;i += lowbit(i))
sum1[i] += y,sum2[i] += x*y;
}
ll getsum(ll x)
{
ll ans = 0;
for(ll i = x;i;i -= lowbit(i))
ans += (x+1)*sum1[i] - sum2[i];
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> m;
for(ll i = 1,a;i <= n;i++)
{
cin >> a;
update(i,a-last);
last = a;
}
while(m--)
{
ll a,l,r,k;
cin >> a >> l >> r;
if(a == 1)
{
cin >> k;
update(l,k);
update(r+1,-k);
}
else
cout << getsum(r) - getsum(l-1) << endl;
}
}
进阶操作
4.求逆序对
利用离散化思想和树状数组的特性
也可以用分治思想:归并排序 --> 代码详解
模板题
模板代码
#include <bits/stdc++.h>
inline long long read(){char c = getchar();long long x = 0,s = 1;
while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
return x*s;}
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x)&(-x)
const int N = 5e5 + 10;
const long long INFINF = 0x7f7f7f7f7f7f7f;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const unsigned long long mod = 998244353;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
struct node
{
ll val,ans;
}k[N];
bool cmp(node a,node b)
{
if(a.val == b.val)
return a.ans < b.ans;
return a.val < b.val;
}
ll n,Rank[N],arr[N];
void update(int x,int y)
{
while(x <= n)
{
arr[x]++;
x += lowbit(x);
}
}
ll getsum(int x)
{
ll ans = 0;
while(x)
{
ans += arr[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> k[i].val;
k[i].ans = i;
}
sort(k+1,k+n+1,cmp);
for(int i = 1;i <= n;i++)
Rank[k[i].ans] = i;
ll ans = 0;
for(int i = 1;i <= n;i++)
{
update(Rank[i],1);
ans += i-getsum(Rank[i]);
}
cout << ans << endl;
}
5.求最大值
void Update(int i,int v)
{
while(i<=maxY)
{
t[i] = max(t[i],v);
i += lowbit(i);
}
}
int query(int i)
{
int ans = 0;
while(i)
{
ans = max(ans,t[i]);
i -= lowbit(i);
}
return ans;
}