除法

这一题我从12.3考ccf之前就在练了。曾花了一晚上看懂了树状数组，被其内在的数学美，神奇的二分思想震惊到了。但是当时我用Java去实现它时却运行错误。

今天我用c++重新实现了它，并且也报错。终于我明白为什么了。

 1 #include <cstdio>
 2 #include <memory.h>
 3 #include <cmath>
 4 #include <string>
 5 #include <vector>
 6 #include <set>
 7 #include <stack>
 8 #include <queue>
 9 #include <algorithm>
10 #include <map>
11 
12 
13 #define I scanf
14 #define OL puts
15 #define O printf
16 #define F(a,b,c) for(a=b;a<c;a++)
17 #define FF(a,b) for(a=0;a<b;a++)
18 #define FG(a,b) for(a=b-1;a>=0;a--)
19 #define LEN 101024
20 #define MAX 0x7FFFFFFF
21 
22 using namespace std;
23 typedef long long ll;
24 int lowbit(int x);
25 void update(int p,int v);
26 ll sum(int p);
27 
28 int a[LEN];
29 ll tree[LEN];
30 int n;
31 
32 int main(){
33     freopen("d:/input/ccf/除法.txt","r",stdin);
34     int m;
35     scanf("%d %d",&n,&m);
36     int i;
37     for(i=1;i<=n;i++){
38         int t;
39         scanf("%d",&t);
40         a[i]=t;
41         update(i,t);
42     }
43     while(m-->0){
44         int opt,l,r,v;
45         scanf("%d %d %d",&opt,&l,&r);
46         if(opt==2){//sum
47             O("%lld
",sum(r)-sum(l-1));
48         }else{//modify
49             scanf("%d",&v);
50             if(v==1) continue;
51             for(i=l;i<=r;i++) if(a[i]>=v && a[i]%v==0){
52                 update(i,a[i]/v-a[i]);
53                 a[i]/=v;
54             }
55 
56         }
57     }
58     return 0;
59 }
60 
61 int lowbit(int x){
62     return -x&x;
63 }
64 
65 void update(int p,int v){
66     while(p<=n){
67         tree[p]+=v;
68         p+=lowbit(p);
69     }
70 }
71 
72 ll sum(int p){
73     ll sum=0;
74     while(p>0){
75         sum+=tree[p];
76         p-=lowbit(p);
77     }
78     return sum;
79 }

1. 树状数组、求和函数都要用64位整数。

2. 数据范围为1e5，声明的原数组和树状数组都初始化1e5的长度

需要注意的点：

　　1.根据数据范围估算程序运行时间，选择合适的算法

　　2.注意有大量求和、相乘的场合，虽然录进去的数据在1e9之内（32位整数最大为2e10），但是结果会超过32位整数范围，应使用64位整数

需要拓展的点：

　　1.高级数据结构