浅说线性差分和树上差分

目录

• 线性差分
  
  
  
  • 正常思路
    
  • 差分思路
    
  • 二维差分的定义
    
  • 二维差分的解释
    
  • 例题1 地毯
    
  
  
• 树上差分引入
  
• 点差分
  
  
  
  • 例题1——wwx的出玩
    
    
    
    • 分析与解答
      
    
    
  • 例题2——松鼠的新家
    
    
    
    • 分析与解答
      
    
    
  
  
• 边差分
  
  
  
  • 例题1——边差分模版
    
    
    
    • 分析与解答
      
    
    
  • 例题2——运输计划
    
    
    
    • 分析与解答
      
    
    
  
  

线性差分

当我们这里有\(n\)个数，现在我要对其中一段进行操作，每次可能加上一个数，也有可能减去一个数，请输出最终的数列。
(\(0\le n \le 10^6\))
正常思路

我们正常来看，如果想要对一个区间进行操作，我们只能遍历这个区间，一个一个的去修改，但是这样的的时间复杂度是\(O(n^2)\)，是过不了的，所以我们要换个思路。（当然如果你只想骗点分也是可以的）
[code]#includeusing namespace std;const int INF=1e7;int a[INF]int main(){        int n,m;        cin>>n>>m;        for (int i=1;i>a;        }        for (int i=1;i>l>>r>>x;                for (int j=l;j>m;        for (int i=1;i>a;                b=a-a[i-1];//计算差分数组        }        for (int i=1;i>l>>r>>c;                b[l]+=c;//核心代码                b[r+1]-=c;        }        for (int i=1;ia;                b=a-a[i-1];        }         for (int i=1;i>x>>y>>z;                b[x]+=z;                b[y+1]-=z;        }        for (int i=1;ia;                if (i==1)continue;                long long c=a-a[i-1];//求解差值                if (c>0)ans1+=c;//判断是正是负                else ans2+=abs(c);        }        coutx1>>y1>>x2>>y2;                mp[x1][y1]++;                mp[x1][y2+1]--;                mp[x2+1][y1]--;                mp[x2+1][y2+1]++;        }        for (int i=1;i>v>>x;                int root=lca(u,v);                p+=x,p[v]+=x,p[root]-=2*x;        }        get(1,-1);        coutn>>m;        for (int i=1;i>u>>v>>w;                mp.push_back({v,w});                mp[v].push_back({u,w});                maxlen=max(maxlen,w);//找到最大的边来求上下边界的值        }        deep[1]=1;        prepare(1,-1);        for (int i=1;i>a>>b;                dis=lca_length(a,b);//维护路径                maxtot=max(dis,maxtot);//找到最大的路径来求上下边界的值        }        int l=maxtot-maxlen,r=300000000;        while (l>1;                for (int i=1;imid){//不符合条件，开始差分                                int root=lca_root(a,b);                                p[a]++,p[b]++,p[root]-=2;                                tim++;//记录次数                        }                }                if (tim==0){//如果都符合，那么当前答案自然可以                        ans=mid;                        r=mid-1;                        continue;                 }                get(1,-1);//求子树和                if (maxtot-maxn