线段树简单题：区间乘积，单点修改
这题其实难度和之前的一样本来不想做的，但是学习了高手的代码，所以自己想实现一遍
果然用了新的代码风格，时间大大提高，空间都减少，不过代码量好像没怎么变，一口气冲进了第10名
| 10 | G-rated | 281MS | 1280K | 1572B | C++ | 2013-01-31 12:57:58 |
#include <cstdio> #define N 50010 const int MOD=1000000007; __int64 mul[4*N]; int n,m; void updata(int a ,int b ,int p ,int e ,int root) { if(a==b) { mul[root]=e; return ; } int mid=(a+b)>>1; if(p<=mid) updata(a,mid,p,e,root<<1); else updata(mid+1,b,p,e,root<<1|1); mul[root]=(mul[root<<1]*mul[root<<1|1])%MOD; return ; } __int64 query(int a ,int b ,int l ,int r ,int root) { int mid=(a+b)>>1; if(a==l && b==r) return mul[root]; if(r<=mid) return query(a,mid,l,r,root<<1); else if(l>mid) return query(mid+1,b,l,r,root<<1|1); else return (query(a,mid,l,mid,root<<1)*query(mid+1,b,mid+1,r,root<<1|1))%MOD; } void build(int a ,int b , int root) { if(a==b) { scanf("%I64d",&mul[root]); //printf("[%d , %d] , %d\n",a,b,mul[root]); return ; } int mid=(a+b)>>1; build(a,mid,root<<1); build(mid+1,b,root<<1 | 1); mul[root]=(mul[root<<1]*mul[root<<1 | 1])%MOD; //printf("[%d , %d] , %d\n",a,b,mul[root]); return ; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); build(1,n,1); scanf("%d",&m); while(m--) { int k,a,b; scanf("%d%d%d",&k,&a,&b); if(!k) //查询区间乘积 printf("%I64d\n",query(1,n,a,b,1)); else //更改单点数值 updata(1,n,a,b,1); } } return 0; }
关于query函数的另一个写法
实际上我更喜欢上面的写法，因为更容易理解，符合人的思维。而且从时间上看，上面的写法比接下来的这个写法要更快。
不过这个写法代码量就少一些
这个写法是基于线段树的性质：线段树中任意两个节点的关系要么是包含关系，要么是相离关系，不可能出现相交
__int64 query(int a ,int b ,int l ,int r ,int root) { if(r<a || l>b) return 1; //完全无交集 if(l<=a && b<=r) return mul[root]; int mid=(a+b)>>1; return (query(a,mid,l,r,root<<1)*query(mid+1,b,l,r,root<<1|1))%MOD; }