题意
求区间和,单点修改。
思路
典型的线段树问题,线段树的实现原理这里不再赘述。
代码
这份代码使用了zkw的非递归堆存储自底向上式线段树,实现难度较低。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <stack> using namespace std; #define MAXN 2097154 int tree[MAXN]; int M = 1; void tree_init(int num){ M = 1; for (; M <= num; M <<= 1); M <<= 1; memset(tree, 0, sizeof(int)*2*M+5); M--; } int tree_query(unsigned int from,unsigned int to){ from--,to++; from += M,to += M; int res = 0; while (from^to^1) { //cout << "+" << from << "+" << to << '~' << endl; if (~from & 1) {//这里是按位取反,不是负号,也不能和0与那样的话肯定是0啊 //from on left res += tree[from+1]; } if (to & 1) { //to on right res += tree[to-1]; } from >>= 1,to >>= 1; } return res; } void tree_update(unsigned int nodeNum,int delta){ nodeNum += M; tree[nodeNum] += delta; while (nodeNum != 1) { nodeNum >>= 1; tree[nodeNum] = tree[nodeNum << 1] + tree[(nodeNum << 1) + 1]; } } int main(){ int casecnt; scanf(" %d",&casecnt); for (int k = 1; k <= casecnt; k++) { int n = 0; scanf(" %d",&n); tree_init(n); for (int i = 1; i <= n; i++) { int arg; scanf(" %d",&arg); tree_update(i+1, arg); } printf("Case %d:\n",k); while (true) { char cmd[6]; memset(cmd, 0, sizeof(cmd)); int arg1 = 0,arg2 = 0; scanf(" %s",cmd); if (cmd[0] == 'Q') { scanf(" %d %d",&arg1,&arg2); printf("%d\n",tree_query(arg1+1, arg2+1)); }else if(cmd[0] == 'A') { scanf(" %d %d",&arg1,&arg2); tree_update(arg1+1, arg2); }else if(cmd[0] == 'S'){ scanf(" %d %d",&arg1,&arg2); tree_update(arg1+1, arg2*-1); }else { break; } } } return 0; } |
January 21, 2015
来传送门
January 21, 2015
自己搜一下题号嘛。。。