本文主要是介绍poj 3468..(存线段树个人模板（自敲）pushdown函数还不理解)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段树很重要！！！
#include<iostream>
#include<cstdio>using namespace std;
int a[100005];struct node
{int l,r,Min,mid;long long sum,add;
}s[500010];void pushDown(int idx){ long long tmp = s[idx].add; int l = idx << 1, r = (idx << 1) ^ 1; s[l].add += tmp; s[l].sum += (s[l].r - s[l].l + 1) * tmp; s[r].add += tmp; s[r].sum += (s[r].r - s[r].l + 1) * tmp; s[idx].add = 0;
}void build(int id,int l,int r)
{s[id].l=l;s[id].r=r;s[id].mid=(l+r)/2;s[id].add=0;if(l==r){s[id].sum=a[l]; s[id].Min=a[l];return;}else{build(id*2,l,(l+r)/2);build(id*2+1,(l+r)/2+1,r);s[id].sum=s[id*2].sum+s[id*2+1].sum;s[id].Min=min(s[id*2].Min,s[id*2+1].Min);}
}//int query(int id,int l,int r)//单点查询
//{
// if((l<=s[id].l)&&(r>=s[id].r))
// return s[id].Min;
//
// else if(l>s[id].mid)
// return query(id*2+1,l,r);
//
// else if(r<=s[id].mid)
// return query(id*2,l,r);
//
// else
// return min(query(id*2+1,l,r),query(id*2,l,r));
//}//void up(int id,int l,int r,int ind,int add)//单点更新
//{
// if(l==r)
// {
// s[id].Min+=add;
// return ;
// }
// int m=(l+r)/2;
// if(ind<=m)
// up(id*2,l,m,ind,add);
// else
// up(id*2+1,m+1,r,ind,add);
//
// s[id].Min=min(s[id*2].Min,s[id*2+1].Min);
//}void update(int idx, int l, int r, int val) //区间更新
{ if((s[idx].r < l)||(s[idx].l > r)) return ; if(s[idx].l >= l&&s[idx].r <= r){ s[idx].sum += (s[idx].r - s[idx].l + 1) * val; s[idx].add += val; return ; } if(s[idx].add != 0) pushDown(idx); update(idx * 2, l, r, val); update(idx * 2 + 1, l, r, val); s[idx].sum = s[idx * 2].sum + s[idx * 2 + 1].sum;
}long long query(int idx, int l, int r) //区间查询
{ if(s[idx].r < l||s[idx].l > r) return 0; if(s[idx].l >= l&&s[idx].r <= r) return s[idx].sum; if(s[idx].add != 0) pushDown(idx); long long x = query(idx * 2, l, r); long long y = query(idx * 2 + 1, l, r); return x + y;
} int main()
{int n, i, q, l, r;long long t; char ord; while(~scanf("%d%d", &n, &q)){ for(i = 1;i <= n;i++) scanf("%lld", &a[i]); build(1, 1, n); while(q--){ scanf("\n%c", &ord); if(ord == 'Q'){ scanf("%d%d", &l, &r); printf("%lld\n", query(1, l, r)); } else { scanf("%d %d %lld", &l, &r, &t); update(1, l, r, t); } } } return 0;
}
// for(int i=1;i<=20;i++) a[i]=i;
//
// for(int i=1;i<=20;i++) printf("%d ",a[i]);
//
// build(1,1,20);
//
// up(1,1,20,4,30);
//
// printf("%d\n",query(1,1,20));
//
// //up(1,1,20,4,-40);
//
// printf("%d\n",query(1,2,20));
//
// //up(1,1,5,2,12);
//
// printf("%d\n",query(1,4,20));
//
// //up(1,1,5,2,12);
//
// printf("%d\n",query(1,5,20));
// for(int i=1;i<=20;i++) printf("%d ",a[i]);
//
// //freopen("in.txt","r",stdin);int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);build(1,1,n);int t;scanf("%d",&t);for(int i=0;i<t;i++){int a,b;scanf("%d %d",&a,&b);//cin>>a>>b;if(a<b)printf("%d\n",query(1,a,b));else if(a>=b)printf("%d\n",query(1,b,a));}
//
//
//
//
//
//
// return 0;
//}这篇关于poj 3468..(存线段树个人模板（自敲）pushdown函数还不理解)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
