Java教程

线段树区间修改,区间查询sin

本文主要是介绍线段树区间修改,区间查询sin,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

传送门

传送门2

 

 

 

 

 

/*

 sin(x + v) = sinx*cosv+sinvcosx

 cos(x + v) = cosx*cosv-sinx*sinv

 

 sin(x1 + v) + sin(x2 + v) = cosv*(sinx1+sinx2) + sinv*(cosx1+cosx2)

 cos(x1 + v) + cos(x1 + v) = cosv*(cosx1+cosx2) - sinv*(sinx1+sinx2)

*/

 

#include<iostream>
#include<algorithm>
#include<math.h> 
#include<map>
/*
// sin(x + v) = sinx*cosv+sinvcosx
// cos(x + v) = cosx*cosv-sinx*sinv

// sin(x1 + v) + sin(x2 + v) = cosv*(sinx1+sinx2) + sinv*(cosx1+cosx2)
// cos(x1 + v) + cos(x1 + v) = cosv*(cosx1+cosx2) - sinv*(sinx1+sinx2)
*/
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
struct node{
    int l,r;
    double sinsum,cossum;
    double lazy;
}t[maxn];
const double eps=1e-8;
double a[maxn];
void push(int p){
    double sinval,cosval,tsin,tcos;
    if(fabs(t[p].lazy)>eps){
        tsin=sin(t[p].lazy);
        tcos=cos(t[p].lazy);
        sinval=t[2*p].sinsum;
        cosval=t[2*p].cossum; 
        t[2*p].sinsum=tsin*cosval+tcos*sinval;
        t[2*p].cossum=tcos*cosval-tsin*sinval;
        t[2*p].lazy+=t[p].lazy;
        
        sinval=t[2*p+1].sinsum;
        cosval=t[2*p+1].cossum;
        t[2*p+1].sinsum=tsin*cosval+tcos*sinval;
        t[2*p+1].cossum=tcos*cosval-tsin*sinval;
        t[2*p+1].lazy+=t[p].lazy;
        
        t[p].lazy=0.0;
    } 
}
void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    t[p].lazy=0.0;
    if(l==r){
        t[p].sinsum=1.0*sin(a[l]);
        t[p].cossum=1.0*cos(a[l]);
        return ;
    }
    int mid=(t[p].l+t[p].r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    t[p].sinsum=t[2*p].sinsum+t[2*p+1].sinsum;
    t[p].cossum=t[2*p].cossum+t[2*p+1].cossum;
}
void add(int p,int l,int r,double k){
    double sinval,cosval,tsin,tcos;
    if(l<=t[p].l&&r>=t[p].r){
        sinval=sin(k),cosval=cos(k),tsin=t[p].sinsum,tcos=t[p].cossum;    
        t[p].lazy+=k;
        t[p].sinsum=tsin*cosval+tcos*sinval;
        t[p].cossum=tcos*cosval-tsin*sinval;
        return ; 
    }
    int mid=(t[p].l+t[p].r)/2;
    push(p);
    if(l<=mid){
        add(2*p,l,r,k);
    }
    if(r>mid){
        add(2*p+1,l,r,k);
    }
    t[p].sinsum=t[2*p].sinsum+t[2*p+1].sinsum;
    t[p].cossum=t[2*p].cossum+t[2*p+1].cossum;
}
double query(int p,int l,int r){
    if(t[p].l>=l&&t[p].r<=r){
        return t[p].sinsum;
    }
    double ans=0.0;
    int mid=(t[p].l+t[p].r)/2;
    push(p);
    if(l<=mid){
        ans+=query(2*p,l,r);
    }
    if(r>mid){
        ans+=query(2*p+1,l,r);
    } 
    return ans;
} 
int main(){
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lf",&a[i]);
    }
    build(1,1,n);
    cin>>m;
    int op,x,y;
    double c;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){
            scanf("%lf",&c);
            add(1,x,y,c);
        }
        else{
            double ans=query(1,x,y);
            printf("%.1lf\n",ans);
        }
    }
} 

 

这个题要维护两个值就是区间sin和 和 区间cos和

 

#include<iostream>#include<algorithm>#include<math.h> #include<map>/*// sin(x + v) = sinx*cosv+sinvcosx// cos(x + v) = cosx*cosv-sinx*sinv
// sin(x1 + v) + sin(x2 + v) = cosv*(sinx1+sinx2) + sinv*(cosx1+cosx2)// cos(x1 + v) + cos(x1 + v) = cosv*(cosx1+cosx2) - sinv*(sinx1+sinx2)*/using namespace std;typedef long long ll;const int maxn=1e6+100;struct node{int l,r;double sinsum,cossum;double lazy;}t[maxn];const double eps=1e-8;double a[maxn];void push(int p){double sinval,cosval,tsin,tcos;if(fabs(t[p].lazy)>eps){tsin=sin(t[p].lazy);tcos=cos(t[p].lazy);sinval=t[2*p].sinsum;cosval=t[2*p].cossum; t[2*p].sinsum=tsin*cosval+tcos*sinval;t[2*p].cossum=tcos*cosval-tsin*sinval;t[2*p].lazy+=t[p].lazy;sinval=t[2*p+1].sinsum;cosval=t[2*p+1].cossum;t[2*p+1].sinsum=tsin*cosval+tcos*sinval;t[2*p+1].cossum=tcos*cosval-tsin*sinval;t[2*p+1].lazy+=t[p].lazy;t[p].lazy=0.0;} }void build(int p,int l,int r){t[p].l=l;t[p].r=r;t[p].lazy=0.0;if(l==r){t[p].sinsum=1.0*sin(a[l]);t[p].cossum=1.0*cos(a[l]);return ;}int mid=(t[p].l+t[p].r)/2;build(2*p,l,mid);build(2*p+1,mid+1,r);t[p].sinsum=t[2*p].sinsum+t[2*p+1].sinsum;t[p].cossum=t[2*p].cossum+t[2*p+1].cossum;}void add(int p,int l,int r,double k){double sinval,cosval,tsin,tcos;if(l<=t[p].l&&r>=t[p].r){sinval=sin(k),cosval=cos(k),tsin=t[p].sinsum,tcos=t[p].cossum;t[p].lazy+=k;t[p].sinsum=tsin*cosval+tcos*sinval;t[p].cossum=tcos*cosval-tsin*sinval;return ; }int mid=(t[p].l+t[p].r)/2;push(p);if(l<=mid){add(2*p,l,r,k);}if(r>mid){add(2*p+1,l,r,k);}t[p].sinsum=t[2*p].sinsum+t[2*p+1].sinsum;t[p].cossum=t[2*p].cossum+t[2*p+1].cossum;}double query(int p,int l,int r){if(t[p].l>=l&&t[p].r<=r){return t[p].sinsum;}double ans=0.0;int mid=(t[p].l+t[p].r)/2;push(p);if(l<=mid){ans+=query(2*p,l,r);}if(r>mid){ans+=query(2*p+1,l,r);} return ans;} int main(){int n,m;cin>>n;for(int i=1;i<=n;i++){scanf("%lf",&a[i]);}build(1,1,n);cin>>m;int op,x,y;double c;for(int i=1;i<=m;i++){scanf("%d%d%d",&op,&x,&y);if(op==1){scanf("%lf",&c);add(1,x,y,c);}else{double ans=query(1,x,y);printf("%.1lf\n",ans);}}} 

这篇关于线段树区间修改,区间查询sin的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!