树状数组

 1 #include<iostream>
 2 #include<cstring>
 3 #include<stdio.h>
 4 
 5 using namespace std; 
 6 
 7 typedef long long ll;
 8 
 9 // 空间要开够...... 
10 // 如果实在装不下, 就得将稀疏数据收紧, 还是不行, 就线段树吧... 
11 const ll MAXN = 1e6+9;
12 ll a[MAXN];
13 ll c[MAXN];
14 ll ret[MAXN];
15 ll n;
16 
17 // int lowbit(int x) {return x&(x^(x–1));}
18 
19 // 注意 x 不能为 0, 因为 0&0 = 0
20 int lowbit(int x) {return x&(-x);}
21 
22 // 前 n 项和 
23 int Sum(int n)
24 {
25     int s = 0;
26     while(n > 0)
27     {
28         s +=  c[n];
29         n -= lowbit(n);
30     }
31     return s;
32  } 
33 
34 // 修改节点值 
35 void change(int i, int x)
36 {    // 居然是这个 MAXN 在作怪..., 算了, 先背下来 
37     while(i <= MAXN)
38     {    
39         c[i] += x;
40         i += lowbit(i);
41     }
42 }
43 
44 // 查询区间 (l-1, r) 的和：区间和 
45 int find_interval(int l, int r)
46 { 
47     return Sum(r) - Sum(l-1);
48 }
49 
50 void fun(int n)
51 {
52     memset(ret, 0, sizeof(ret));
53     memset(c, 0, sizeof(c));
54     for(int i=1;i<=n;i++){
55         scanf("%d", &a[i]);
56         change(a[i], i);
57     }
58     for(int i=1;i<=n;i++)
59         cout<<Sum(i)<<endl;
60     return;
61 }
62 
63 int main()
64 {
65     while(cin>>n)
66     { 
67         fun(n);    
68     }
69     
70     return 0;
71 }
2019-02-22
21:07:22