hdu 3074 线段树 OR 树状数组

比较基础的线段树，1A。

线段树：

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 
  6 typedef long long ll;
  7 const int N = 50001;
  8 const int MOD = 1000000007;
  9 int a[N];
 10 
 11 struct Node
 12 {
 13     int l, r, s;
 14 } node[N << 2];
 15 
 16 void pushup( int i )
 17 {
 18     node[i].s = ( ll ) node[i << 1].s * node[i << 1 | 1].s % MOD;
 19 }
 20 
 21 void build( int i, int l, int r )
 22 {
 23     node[i].l = l, node[i].r = r;
 24     if ( l == r )
 25     {
 26         node[i].s = a[l];
 27         return ;
 28     }
 29     int mid = ( l + r ) >> 1;
 30     build( i << 1, l, mid );
 31     build( i << 1 | 1, mid + 1, r );
 32     pushup(i);
 33 }
 34 
 35 void update( int i, int pos, int val )
 36 {
 37     if ( node[i].l == pos && node[i].r == pos )
 38     {
 39         node[i].s = val;
 40         return ;
 41     }
 42     int mid = ( node[i].l + node[i].r ) >> 1;
 43     if ( pos <= mid )
 44     {
 45         update( i << 1, pos, val );
 46     }
 47     else
 48     {
 49         update( i << 1 | 1, pos, val );
 50     }
 51     pushup(i);
 52 }
 53 
 54 int query( int i, int l, int r )
 55 {
 56     if ( node[i].l == l && node[i].r == r ) return node[i].s;
 57     int mid = ( node[i].l + node[i].r ) >> 1;
 58     if ( r <= mid )
 59     {
 60         return query( i << 1, l, r );
 61     }
 62     else if ( l > mid )
 63     {
 64         return query( i << 1 | 1, l, r );
 65     }
 66     else
 67     {
 68         return ( ll ) query( i << 1, l, mid ) * query( i << 1 | 1, mid + 1, r ) % MOD;
 69     }
 70 }
 71 
 72 int main ()
 73 {
 74     int t;
 75     scanf("%d", &t);
 76     while ( t-- )
 77     {
 78         int n, m;
 79         scanf("%d", &n);
 80         for ( int i = 1; i <= n; i++ )
 81         {
 82             scanf("%d", a + i);
 83         }
 84         build( 1, 1, n );
 85         scanf("%d", &m);
 86         while ( m-- )
 87         {
 88             int op, a, b;
 89             scanf("%d%d%d", &op, &a, &b );
 90             if ( op == 0 )
 91             {
 92                 printf("%d
", query( 1, a, b ));
 93             }
 94             else
 95             {
 96                 update( 1, a, b );
 97             }
 98         }
 99     }
100     return 0;
101 }

当然，对于这种单点修改和查询区间“前缀和”的问题，我们自然也可以用树状数组来做，不过要用到乘法逆元。

对于这道题来说，树状数组反而难写，并且时间上也没有什么优势。

不过这是一种思想，将“加法”扩展到了“乘法”。

也可以考虑用log把乘法变成加法，不过可能会有精度问题。

树状数组：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int N = 50001;
 8 const int MOD = 1000000007;
 9 int a[N];
10 int c[N];
11 
12 void extgcd( int a, int mod, int &x, int &y )
13 {
14     if ( !mod )
15     {
16         x = 1, y = 0;
17     }
18     else
19     {
20         extgcd( mod, a % mod, y, x );
21         y -= x * ( a / mod );
22     }
23 }
24 
25 int lb( int i )
26 {
27     return i & -i;
28 }
29 
30 void update( int i, int x )
31 {
32     while ( i < N )
33     {
34         c[i] = ( ll ) c[i] * x % MOD;
35         i += lb(i);
36     }
37 }
38 
39 int get( int i )
40 {
41     int ans = 1;
42     while ( i )
43     {
44         ans = ( ll ) ans * c[i] % MOD;
45         i -= lb(i);
46     }
47     return ans;
48 }
49 
50 int main ()
51 {
52     int t;
53     scanf("%d", &t);
54     while ( t-- )
55     {
56         int n, m;
57         scanf("%d", &n);
58         for ( int i = 1; i <= n; i++ )
59         {
60             c[i] = 1;
61         }
62         for ( int i = 1; i <= n; i++ )
63         {
64             scanf("%d", a + i);
65             update( i, a[i] );
66         }
67         scanf("%d", &m);
68         while ( m-- )
69         {
70             int op, x, y, inv, useless;
71             scanf("%d%d%d", &op, &x, &y );
72             if ( op == 0 )
73             {
74                 extgcd( get( x - 1 ), MOD, inv, useless );
75                 inv = ( inv + MOD ) % MOD;
76                 int tmp = ( ll ) inv * get(y) % MOD;
77                 printf("%d
", tmp);
78             }
79             else
80             {
81                 extgcd( a[x], MOD, inv, useless );
82                 inv = ( inv + MOD ) % MOD;
83                 inv = ( ll ) inv * y % MOD;
84                 a[x] = ( ll ) a[x] * inv % MOD;
85                 update( x, inv );
86             }
87         }
88     }
89     return 0;
90 }