解题思路:
线段树的基础操作,线段树的特点是左右子节点管理父节点的管理区间的一半。
查询思路:如果查询区间完全覆盖了当前节点管理的区间,则直接返回;否则判断是否与子节点管理区间有
交集,如果有则递归判断。
建树和更新思路:当我们更新某个节点值时(建树可以看作将叶子节点更新),最终都会更新根节点,
所以实现时可以以根作为递归入口,更新其子节点后再更新自己。
注意事项:
线段树的大小一半取2n左右 详细见https://www.luogu.com.cn/discuss/show/52150
参考代码:
/* *数列操作:线段树 *!!线段树下标从1开始 */ #include<cstdio> const int Max_N = 100000; int n,m; int a[Max_N+1]; int tree[(Max_N<<2)+1]; void build(int k, int l, int r); //建立线段树 int query(int L, int R, int k, int l, int r); //查询 void updatePoint(int p, int v, int k, int l, int r); //更新点 void pushUp( int k ); //向上更新 int main() { scanf("%d%d",&n,&m); for( int i=1; i<=n; i++ ) scanf("%d",&a[i]); build(1,1,n); while( m-- ) { int k,l,r; scanf("%d%d%d",&k,&l,&r); if( k==0 ) { printf("%d\n",query(l,r,1,1,n)); } else { updatePoint(l,r,1,1,n); } } return 0; } void build(int k, int l, int r) { if( l==r ) { tree[k] = a[l]; } else { int m = l + ((r-l)>>1); build(k<<1,l,m); build(k<<1|1,m+1,r); pushUp(k); } } void pushUp(int k) { tree[k] = tree[k<<1] + tree[k<<1|1]; } void updatePoint(int p, int v, int k, int l, int r) { if( l==r ) { tree[k] += v; } else { int m = l + ((r-l)>>1); if( p<=m ) updatePoint(p,v,k<<1,l,m); else updatePoint(p,v,k<<1|1,m+1,r); pushUp(k); } } int query(int L, int R, int k, int l, int r) { if( L<=l && r<=R ) { return tree[k]; } else { int m = l + ((r-l)>>1); int res = 0; if( L<=m && R>=l ) res += query(L,R,k<<1,l,m); if( L<=r && R>m ) res += query(L,R,k<<1|1,m+1,r); return res; } }
0.0分
4 人评分
C二级辅导-统计字符 (C语言代码)浏览:729 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:1066 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:525 |
printf基础练习2 (C语言代码)浏览:567 |
C语言训练-斐波纳契数列 (C语言代码)浏览:1160 |
A+B for Input-Output Practice (III) (C语言代码)浏览:569 |
【排队买票】 (C语言代码)浏览:898 |
1126题解浏览:577 |
演讲大赛评分 (C语言代码)浏览:1627 |
复数求和 (C语言代码)浏览:915 |