线段树（树状数组进阶）_C

1.树状数组 1：

题源在这里哦

题解分析：

首先每块区间分下去，所需要的答案是一段的，正常算法复杂度会很大，线段树可以将复杂度降低到O（mlongn)，以下的AC代码，有部分注释

AC代码：

#include
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define inf_max 0x7f7f7f7f
typedef long long ll;
///线段树
int a[2000005],f[2000005];//a用于存节点数据，f用于存1-k的线段和
//建立一棵树
inline void buildtree(int k,int l,int r){
    if(l==r){
        f[k]=a[l];
        return;
    }
    int m=l+((r-l)>>1);
    buildtree(k+k,l,m);
    buildtree(k+k+1,m+1,r);
    f[k]=f[k+k]+f[k+k+1];
}
//add 对x上加一个y，那么1-x下标的f都要加上y
inline void add(int k,int l,int r,int x,int y){
    f[k]+=y;
    if(l==r)return;
    int m=l+((r-l)>>1);
    if(x>m)
        return add(k+k+1,m+1,r,x,y);
    else
        return add(k+k,l,m,x,y);
}
//对x-y区间的数字求和，那么就是在l，r区间找到x,y的和
inline int calc(int k,int l,int r,int x,int y){
    if(l==x&&r==y)
        return f[k];
    int m=l+((r-l)>>1);
    if(x>m)
        return calc(k+k+1,m+1,r,x,y);
    else
        if(y<=m)
            return calc(k+k,l,m,x,y);
        else
            return calc(k+k,l,m,x,m)+ calc(k+k+1,m+1,r,m+1,y);
}
void Solve() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    buildtree(1,1,n);
    for(int i=1;i<=m;++i)
    {
        int t,x,y;
        cin>>t>>x>>y;
        if(t==1)
            add(1,1,n,x,y);
        else
            cout<

 
2.线段树1 
题源在这里哦！！ 
 
 
 
      这是一个带标记的线段树，v【k】作为标记数组，如果是单点修改的话，所以就是区间修改，每次修改的复杂度都是logn，那么总体时间复杂度就是O（mnlongn）那么必会炸！！所以用标记数组存数区间x-y需要加的数据，到最后return 在p[k]+(y-x+1)*v[k];优化了整体的时间复杂度；当然本题数据大，我们直接开long long； 
 
AC代码： 
#include
using namespace std;
#define endl '\n'
#define int long long
#define inf 0x3f3f3f3f
#define inf_max 0x7f7f7f7f
typedef long long ll;
///线段树
int a[400005],f[400005],v[400005];

//建树
inline void buildtree(int k,int l,int r){
    v[k]=0;
    if(l==r){
        f[k]=a[l];
        return;
    }
    int m=l+((r-l)>>1);
    buildtree(k+k,l,m);
    buildtree(k+k+1,m+1,r);
    f[k]=f[k+k]+f[k+k+1];
}
//mei ge shu jia shang z(x-y)
inline void insert(int k,int l,int r,int x,int y,  int z){
    if(l==x&&y==r){
        v[k]+=z;
        return ;
    }
    f[k]+=(y-x+1)*z;
    int m=l+((r-l)>>1);
    if(x>m)
        insert(k+k+1,m+1,r,x,y,z);
    else
        if(y<=m)
            insert(k+k,l,m,x,y,z);
        else
            insert(k+k,l,m,x,m,z),
            insert(k+k+1,m+1,r,m+1,y,z);
}
//cacl x-y he
int cacl(int k,int l,int r,int x,int y, int p){
    p+=v[k];
    if(l==x&&y==r)
        return f[k]+(y-x+1)*p;
    int m=l+((r-l)>>1);
    if(x>m)
        return cacl(k+k+1,m+1,r,x,y,p);
    else
        if(y<=m)
            return cacl(k+k,l,m,x,y,p);
        else
            return cacl(k+k,l,m,x,m,p)+ cacl(k+k+1,m+1,r,m+1,y,p);

}
void Solve() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    buildtree(1,1,n);
    for(int i=1;i<=m;++i)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int x,y;
              int z;
            cin>>x>>y>>z;
            insert(1,1,n,x,y,z);
        }else
        {
            int x,y;
            cin>>x>>y;
            cout<
 
核心部分： 
inline void insert(int k,int l,int r,int x,int y,  int z){
    if(l==x&&y==r){
        v[k]+=z;
        return ;
    }
    f[k]+=(y-x+1)*z;
}
//cacl x-y he
int cacl(int k,int l,int r,int x,int y, int p){
    p+=v[k];
    if(l==x&&y==r)
        return f[k]+(y-x+1)*p;
} 

					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/564799.html

线段树（树状数组进阶）

发表评论

评论列表（0条）