首页 > 代码库 > 线段树
线段树
(CodeVS:1082)
C++指针版
#include <iostream> #include <cstdio> #include <cstring> #define ll long long using namespace std; struct rec{ ll l,r,delta,sum; rec *lc,*rc; }; rec *root; ll l,r,add,n,m,tmp; void update(rec *now,ll l,ll r,ll add) { if ((l<=now->l)&&(now->r<=r)) { now->delta+=add; return; } if (l<=(now->l+now->r)/2) update(now->lc,l,r,add); if (r>(now->l+now->r)/2) update(now->rc,l,r,add); now->sum=now->lc->sum+(now->lc->r-now->lc->l+1)*now->lc->delta; now->sum+=now->rc->sum+(now->rc->r-now->rc->l+1)*now->rc->delta; } void build(rec *now,ll l,ll r) { now->l=l;now->r=r; if (l==r) { scanf("%lld",&now->sum); now->lc=NULL;now->rc=NULL; return; } now->lc=new rec; now->rc=new rec; build(now->lc,l,(l+r)/2); build(now->rc,(l+r)/2+1,r); now->sum=now->lc->sum+now->rc->sum; } ll query(rec *now,ll l,ll r) { ll ret=0; if ((l<=now->l)&&(now->r<=r))return now->sum+now->delta*(now->r-now->l+1); now->lc->delta+=now->delta; now->rc->delta+=now->delta; now->sum+=now->delta*(now->r-now->l+1); now->delta=0; if (l<=(now->l+now->r)/2)ret=query(now->lc,l,r); if (r>(now->r+now->l)/2)ret+=query(now->rc,l,r); return ret; } int main() { root=new rec; scanf("%lld",&n); build(root,1,n); scanf("%lld",&m); for (int i=1;i<=m;i++) { scanf("%lld",&tmp); if (tmp==1) { scanf("%lld %lld %lld",&l,&r,&add); update(root,l,r,add); } if (tmp==2) { scanf("%lld %lld",&l,&r); printf("%lld\n",query(root,l,r)); } } }
线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。