线段树维护区间利用相关公式

1.下面借助一下牛客算法基础训练营线段树和数状数组的一道题叫做开挂;

这道题很明显的考察了线段树的区间维护，和相关公式的利用;

其实是一道很裸的线段树题目，简单看看就需要一个板子就够了，实际上需要一个数学公式如下;

线段树主要是就是注意下一下数学的运用和公式的运用，还有就是写的时候一定要注意，错了真的要debug很久很久，注意的方式可以写一段测试一段保证一段没有错误,下面附上代码：本题会了，线段树相关操作也应该会的差不多了，差的可能是数学的功底，推公式的功底了。

// __ __ _ _ _ _
// | / | | | (_) | | (_)
// | / | __ _| |_ ___ _ __ _ __ _| | _ _______
// | |/| |/ _` | __/ _ '__| |/ _` | | | |_ / _
// | | | | (_| | || __/ | | | (_| | | | |/ / __/
// _| |_/__,_|_____|_| |_|__,_|_| |_/______|
#include
#include
#include
#include
#include
#include
#include
#include
#include
#includeAD
#includec
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef pair PII;
typedef pair PPI;
template void mysort(T &a,T &b){T temp=a;a=b;b=temp;}
struct bigNode {int x,y;bool operator<(const bigNode &a) const{if(x==a.x) return y struct smallNode {int x,y;bool operator<(const smallNode &a) const{if(x==a.x) return y>a.y;else return x>a.x;}};
#define int long long
const int N =100010;
struct Node{
int l,r;
int sum1;//区间的和;
int sum2;//区间和的平方;
//int sum3;//区间的平方和;//这个直接就可以算出来,不需要单独维护,维护起来估计又是公式;
int add;
}t[N*4];
int n,m,op,w[N];
inline void eval(Node &tr,int add){
tr.add+=add;
tr.sum2+=2*add*tr.sum1+add*add*(tr.r-tr.l+1);
tr.sum1+=(tr.r-tr.l+1)*add;//上下两行代码不能颠倒,找了半小时的bug，一直为4;
return ;
}
inline void pushup(int u){
t[u].sum1=(t[u<<1].sum1+t[u<<1|1].sum1);
t[u].sum2=(t[u<<1].sum2+t[u<<1|1].sum2);
return ;
}
inline void pushdown(int u){
if(t[u].add){
eval(t[u<<1],t[u].add);
eval(t[u<<1|1],t[u].add);
t[u].add=0;
return ;
}
}
inline void build(int u,int l,int r){
if(l==r){
t[u]={l,r,w[r],w[r]*w[r],0};
return ;
}
t[u]={l,r,0,0,0};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
inline void modify(int u,int l,int r,int add){
pushdown(u);
if(t[u].l>=l&&t[u].r<=r){
eval(t[u],add);
return ;
}
int mid=t[u].l+t[u].r>>1;
if(l<=mid) modify(u<<1,l,r,add);
if(r>mid) modify(u<<1|1,l,r,add);
pushup(u);
}
inline int query1(int u,int l,int r){
pushdown(u);
if(t[u].l>=l&&t[u].r<=r) return t[u].sum1;
int mid=t[u].l+t[u].r>>1;
int res=0;
if(l<=mid) res+=query1(u<<1,l,r);
if(r>mid) res+=query1(u<<1|1,l,r);
return res;
}
inline int query2(int u,int l,int r){
if(t[u].l>=l&&t[u].r<=r) return t[u].sum2;
pushdown(u);
int mid=t[u].l+t[u].r>>1;
int res=0;
if(l<=mid) res+=query2(u<<1,l,r);
if(r>mid) res+=query2(u<<1|1,l,r);
return res;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
build(1,1,n);
while(m--){
int l,r,x;
cin>>op;
if(op==1) {
cin>>l>>r>>x;
modify(1,l,r,x);
}else {
cin>>l>>r;
int s1=query1(1,l,r);
int s2=query2(1,l,r);
//cout << s1 << " "< cout << (s1*s1-s2)/2< }
}
return 0;
}

线段树维护区间利用相关公式

C/C++/C#相关栏目本月热门文章