引入：用数组模拟树形结构，可以解决一些区间更新，求和的问题。比线段树更简单一些的数据结构，树状数组能够解决的问题，线段树（还没学）都可以解决。
原理啥的，我也讲不明白，看大佬博客
构建树状数组
单点更新，区间查询
int n,a[1000010],c[1000010];int lowbit(int x){return x&-x;//返回二进制最后一位1}void updata(int i,int k){//在i的位置上加上kfor(;i<=n;i+=lowbit(i)) c[i]+=k;}int getsum(int i){//求a[1]-a[i]的和int ans=0;for(;i>0;i-=lowbit(i)) ans+=c[i];return ans;}
来一个模板题
HDU1166
代码：
#include<bits/stdc++.h>using namespace std;int n,a[1000010],c[1000010];int lowbit(int x){return x&-x;}void updata(int i,int k){for(;i<=n;i+=lowbit(i)) c[i]+=k;}int getsum(int i){int ans=0;for(;i>0;i-=lowbit(i)) ans+=c[i];return ans;}int main(){int t;cin>>t;for(int tot=1;tot<=t;tot++){cout<<"Case "<<tot<<":"<<endl;memset(a,0,sizeof a);memset(c,0,sizeof c);cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];updata(i,a[i]);}string s;int x,y;while(cin>>s&&s[0]!='E'){cin>>x>>y;if(s[0]=='Q'){int sum=getsum(y)-getsum(x-1);cout<<sum<<endl;}else if(s[0]=='S'){updata(x,-y);}else if(s[0]=='A'){updata(x,y);}}}}
我的板子好像有问题，以后都不敢用了，TLE一下午不知道咋回事，世界未解之谜，代码还是写简单一些不加乱七八糟的东西，不然debug浪费时间
上面这种情况是单点更新、区间查询
单点更新，单点查询
普通数组就可以了。
区间更新、单点查询
给某一段区间同时加上一个数，最后加之后某个点的值，我们知道在某一个区间加上一个数，可以用差分，这里我们用差分数组建立树状数组。
int n,a[1000010],c[1000010];//a原数组，c差分数组
inline int lowbit(int x){return x&-x;}
void updata(int i,int k){
for(;i<=n;i+=lowbit(i)) c[i]+=k;
}
int getsum(int i){
int ans=0;
for(;i>0;i-=lowbit(i)) ans+=c[i];
return ans;
}
void add(int l,int r,int k){//在区间[l-r]加上一个数k
updata(l,k);
updata(r+1,-k);
}
洛谷P4939
模板题，给你两个操作，0，在给你区间+1，1输出某个点的值。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000010;
int n,a[10000010],c[10000010];//a原数组，c差分数组
inline int lowbit(int x){return x&-x;}
void updata(int i,int k){
for(;i<=n;i+=lowbit(i)) c[i]+=k;
}
int getsum(int i){
int ans=0;
for(;i>0;i-=lowbit(i)) ans+=c[i];
return ans;
}
void add(int l,int r,int k){//在区间[l-r]加上一个数k
updata(l,k);
updata(r+1,-k);
}
signed main(){
int m;
scanf("%lld%lld",&n,&m);
while(m--){
int op,l,r;
scanf("%lld",&op);
if(op&1){
scanf("%lld",&l);
int ans=getsum(l);
printf("%lld\n",ans);
}
else {
scanf("%lld%lld",&l,&r);
add(l,r,1);
}
}
}
洛谷P5057
跟上一题类似，判断最后的奇偶就行了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000010;
int n,a[10000010],c[10000010];//a原数组，c差分数组
inline int lowbit(int x){return x&-x;}
void updata(int i,int k){
for(;i<=n;i+=lowbit(i)) c[i]+=k;
}
int query(int i){
int ans=0;
for(;i>0;i-=lowbit(i)) ans+=c[i];
return ans;
}
void add(int l,int r,int k){//在区间[l-r]加上一个数k
updata(l,k);
updata(r+1,-k);
}
signed main(){
int m;
scanf("%lld%lld",&n,&m);
while(m--){
int op,l,r;
scanf("%lld",&op);
if(op==2){
scanf("%lld",&l);
int ans=getsum(l)&1;
printf("%lld\n",ans);
}
else {
scanf("%lld%lld",&l,&r);
add(l,r,1);
}
}
}
一个简单的整数问题
给了原始数组的模板题，树状数组，区间更新，单点查询。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000010;
int n,a[10000010],c[10000010];//a原数组，c差分数组
inline int lowbit(int x){return x&-x;}
void updata(int i,int k){
for(;i<=n;i+=lowbit(i)) c[i]+=k;
}
int getsum(int i){
int ans=a[i];
for(;i>0;i-=lowbit(i)) ans+=c[i];
return ans;
}
void add(int l,int r,int k){//在区间[l-r]加上一个数k
updata(l,k);
updata(r+1,-k);
}
signed main(){
int m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
while(m--){
int l,r,d;
char op;
cin>>op;//用scanf，多了一个空格，要用getchar吃掉，靠
if(op=='Q'){
scanf("%lld",&l);
int ans=getsum(l);
printf("%lld\n",ans);
}
else if(op=='C'){
scanf("%lld%lld%lld",&l,&r,&d);
add(l,r,d);
}
}
}
区间更新，区间查询
const int N=1000010;
int n,a[1000010],c[1000010];//a原数组，c差分数组
int b1[N],b2[N];
inline int lowbit(int x){return x&-x;}
void updata(int i,int k){
int tmp=i*k;
for(;i<=n;i+=lowbit(i)) b1[i]+=k,b2[i]+=tmp;
}
int query(int b[],int i){
int ans=0;
for(;i>0;i-=lowbit(i)) ans+=b[i];
return ans;
}
void add(int l,int r,int k){//在区间[l-r]加上一个数k
updata(l,k);
updata(r+1,-k);
}
洛谷P2357
做了这一题发现，区间更新，区间查询也可以用于做单点更新单点查询，区间更新，单点查询。
这一题5个操作，1给区间都加一个数，2给 加上一个数，3给
减一个数，4求一个区间的和，5求
的值。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000010;
int n,a[1000010],c[1000010];//a原数组，c差分数组
int b1[N],b2[N];
inline int lowbit(int x){return x&-x;}
void updata(int i,int k){
int tmp=i*k;
for(;i<=n;i+=lowbit(i)) b1[i]+=k,b2[i]+=tmp;
}
int query(int b[],int i){
int ans=0;
for(;i>0;i-=lowbit(i)) ans+=b[i];
return ans;
}
void add(int l,int r,int k){//在区间[l-r]加上一个数k
updata(l,k);
updata(r+1,-k);
}
int query(int l,int r){
return (r+1)*query(b1,r)-query(b2,r)-(l*query(b1,l-1)-query(b2,l-1));
}
signed main(){
int f;
cin>>n>>f;
for(int i=1;i<=n;i++){
cin>>a[i];
b1[i]+=a[i]-a[i-1];
b2[i]+=i*(a[i]-a[i-1]);
int j=i+lowbit(i);
if(j<=n) b1[j]+=b1[i],b2[j]+=b2[i];
}
while(f--){
int op,l,r,k;
cin>>op;
if(op==1){
cin>>l>>r>>k;
add(l,r,k);
}
else if(op==2){
cin>>k;
add(1,1,k);
}
else if(op==3){
cin>>k;
add(1,1,-k);
}
else if(op==4){
cin>>l>>r;
int ans=query(l,r);
cout<<ans<<endl;
}
else{
int ans=query(1,1);
cout<<ans<<endl;
}
}
return 0;
}
洛谷P1908
求逆序对。
树状数组+离散化
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sc(n) scanf("%lld",&n)
#define SC(a,b) scanf("%lld%lld",&a,&b)
#define pr(a) printf("%lld",a)
const int N=1000010;
int n,a[1000010],c[1000010],b[N];
int lowbit(int x){
return x&-x;//返回二进制最后一位1
}
void updata(int i,int k){//在i的位置上加上k
for(;i<=N;i+=lowbit(i)) c[i]+=k;
}
int getsum(int i){//求a[1]-a[i]的和
int ans=0;
for(;i>0;i-=lowbit(i)) ans+=c[i];
return ans;
}
signed main(){
sc(n);
for(int i=1;i<=n;i++) sc(a[i]),b[i]=a[i];//离散化操作
sort(b+1,b+1+n);
int cnt=unique(b+1,b+1+n)-(b+1);
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+1+n,a[i])-b;
}
int ans=0;
for(int i=1;i<=n;i++){
ans+=i-1-getsum(a[i]);//getsum(a[i]) 求得是a[i]之前有多少个比a[i]更小的数，
updata(a[i],1);
}
pr(ans);
return 0;
}
洛谷P1637 三元上升子序列
题意：Erwin 最近对一种叫 thair 的东西巨感兴趣。。。在含有 n 个整数的序列$ a_1,a_2,…,a_n i<j<k$ 且
;求一个序列中
thair 的个数。
输入：
4
2 1 3 4
5
1 2 2 3 4
输出：
2
7
DP+动态规划+离散化
假设
表示以a[j]结尾的长度为 i 的上升子序列的个数。
动态转移方程
,
;
要满足两个性质：
;
求和我们可以用树状数组+离散化来维护，
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sc(n) scanf("%lld",&n)
#define SC(a,b) scanf("%lld%lld",&a,&b)
#define pr(a) printf("%lld",a)
const int N=1000010;
int n,a[1000010],c[1000010],b[N],m,ans,f[4][300010];
//f[i][j]表示以a[j]结尾的长度为i,上升子序列的个数
int lowbit(int x){
return x&-x;//返回二进制最后一位1
}
void updata(int i,int k){//在i的位置上加上k
for(;i<=n;i+=lowbit(i)) c[i]+=k;
}
int getsum(int i){//求a[1]-a[i]的和
int ans=0;
for(;i>0;i-=lowbit(i)) ans+=c[i];
return ans;
}
signed main(){
sc(n);
for(int i=1;i<=n;i++) sc(a[i]),b[i]=a[i];//离散化操作
sort(b+1,b+1+n);
int cnt=unique(b+1,b+1+n)-(b+1);
for(int i=1;i<=n;i++){
f[1][i]=1;//长度为1的个数初始化为1
a[i]=lower_bound(b+1,b+1+n,a[i])-b;//离散化
}
for(int i=2;i<=3;i++){
memset(c,0,sizeof(c));
for(int j=1;j<=n;j++){
f[i][j]=getsum(a[j]-1);//动态转移方程
updata(a[j],f[i-1][j]);
}
}
for(int i=1;i<=n;i++){
ans+=f[3][i];
}
pr(ans);
return 0;
}
力扣1904
题意：给一个序列a,求出以每一个结尾的最长上升子序列的长度。
树状数组+离散化
class Solution {
public:
vector<int> tree;
int n;
int lowbit(int i) {
return i & -i;
}
void update(int id, int x) { // 将id更新为x
while (id <= n) {
tree[id] = max(tree[id], x);
id += lowbit(id);
}
}
int query(int id) {
int ans = 0;
while (id) {
ans = max(ans, tree[id]);
id -= lowbit(id);
}
return ans;
}
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
vector<int> diff = obstacles; // 离散化数组
sort(diff.begin(), diff.end());
n = unique(diff.begin(), diff.end()) - diff.begin();
tree.resize(n + 1, 0);
vector<int> ans;
for (auto& i : obstacles) {
int idx = lower_bound(diff.begin(), diff.begin() + n, i) - diff.begin() + 1;
int res = query(idx);
ans.push_back(res + 1);
update(idx, res + 1);
}
return ans;
}
};
若有收获，就点个赞吧
0 人点赞
