POJ 3468 A Simple Problem with Integers

Desscription

n个数字初始化，执行两种操作：更新与查询

树状数组

设三个不同的前缀和数组：

sum[i]:存原始数组前i项的和

d[i]:存从i到n的增量

di[i]: 存相应的d[i] * i

最终ans分两部分（原始前缀和+变化量前缀和）：

①sum[end] - sum[begin - 1]

②(end + 1) query(d, end) - query(di, end) - {[(b - 1) + 1] query(d, b - 1) - query(di, b - 1)}

分析参考

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;

typedef long long ll;

int n, m;
///三个不同的前缀和数组
ll sum[N];
ll d[N];
ll di[N];

///树状数组：动态维护"前缀和"
int lowbit(int pos)
{
    return pos & -pos;
}

///万能更新(前缀和)
void update(ll * t, int pos, ll val)
{
    while(pos <= n)
    {
        t[pos] += val;
        pos += lowbit(pos);
    }
}

///万能查询(前缀和)
ll query(ll * t, int pos)
{
    long long res = 0;
    while(pos >= 1)
    {
        res += t[pos];
        pos -= lowbit(pos);
    }
    return res;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        memset(sum, 0, sizeof(sum));
        memset(d, 0, sizeof(d));
        memset(di, 0, sizeof(di));
        ll tem;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%lld", &tem);
            sum[i] = sum[i - 1] + tem;
        }
        getchar();
        char ch;
        ll b, c, e;
        while(m--)
        {
            ch = getchar();
            if(ch == 'Q')
            {
                scanf("%lld%lld", &b, &c);
                getchar();
                ll ans = sum[c] - sum[b - 1];
                ans += (c + 1) * query(d, c) - query(di, c);
                ans -= b * query(d, b - 1) - query(di, b - 1);
                cout << ans << '\n';
            }
            else
            {
                scanf("%lld%lld%lld", &b, &c, &e);
                getchar();
                update(d, b, e);
                update(d, c + 1, -e);
                update(di, b, e * b);
                update(di, c + 1, -e * (c + 1));
            }
        }
    }
    return 0;
}
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

线段树（分清存和or存最值）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;

struct node
{
    int L, R;
    long long val, lazy;
} a[N << 2 | 1];

long long ans;

void down(int x)
{
    a[x << 1].val += a[x].lazy * (a[x << 1].R - a[x << 1].L + 1);
    a[x << 1].lazy += a[x].lazy;
    a[x << 1 | 1].val += a[x].lazy * (a[x << 1 | 1].R - a[x << 1 | 1].L + 1);
    a[x << 1 | 1].lazy += a[x].lazy;
    a[x].lazy = 0;
}

void init(int num, int l, int r)
{
    a[num].L = l;
    a[num].R = r;
    a[num].val = 0;
    a[num].lazy = 0;

    if(l == r)///勿忘
        return ;

    int mid = (l + r) >> 1;
    init(num << 1, l, mid);
    init(num << 1 | 1, mid + 1, r);
}

void update(int num, int l, int r, int tot)
{
    if(a[num].L > r || a[num].R < l)
        return ;
    if(a[num].L >= l && a[num].R <= r)
    {
        a[num].val += tot * (a[num].R - a[num].L + 1);
        a[num].lazy += tot;
        return ;
    }
    down(num);
    update(num << 1, l, r, tot);
    update(num << 1 | 1, l, r, tot);
    a[num].val = a[num << 1].val + a[num << 1 | 1].val;
}

long long query(int num, int l, int r)
{
    if(a[num].L == l && a[num].R == r)
        return a[num].val;
    if(a[num].L == a[num].R)
        return 0;

    down(num);///查询与更新都要有的操作
    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        return ans + query(num << 1, l, r);
    else if(mid < l)
        return ans + query(num << 1 | 1, l, r);
    else
        return ans + query(num << 1, l, mid) + query(num << 1 | 1, mid + 1, r);

}

int main()
{
    int n, q;
    while(~scanf("%d%d", &n, &q))
    {
        init(1, 1, n);
        int tem, d;
        int b, c;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &tem);
            update(1, i, i, tem);
        }
        getchar();
        char ch;
        while(q--)
        {
            ch = getchar();
            if(ch == 'Q')
            {
                ans = 0;
                scanf("%d%d", &b, &c);
                getchar();
                cout << query(1, b, c) << '\n';
            }
            else
            {
                scanf("%d%d%d", &b, &c, &d);
                getchar();
                update(1, b, c, d);
            }
        }
    }
    return 0;
}
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

线段树update函数优雅写法

void update(int num, int l, int r, int tot)
{
    if(a[num]. L == l && a[num].R == r)
    {
        a[num].val += tot * (a[num].R - a[num].L + 1);///存和与存最值的不同
        a[num].lazy += tot;
        return ;
    }

    if(a[num].L == a[num].R)
        return ;

    down(num);///此区间非目标区间，数据下传
    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        update(num << 1, l, r, tot);
    else if(mid < l)
        update(num << 1 | 1, l, r, tot);
    else
    {
        ///第三种情况分别找，区间分成两部分
        update(num << 1, l, mid, tot);
        update(num << 1 | 1, mid + 1, r, tot);
    }

    a[num].val = a[num << 1].val + a[num << 1 | 1].val;
}
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

线段树update函数流氓写法

void update(int num, int l, int r, int tot)
{
    if(a[num].L > r || a[num].R < l)
        return ;
    if(a[num].L >= l && a[num].R <= r)
    {
        a[num].val += tot * (a[num].R - a[num].L + 1);
        a[num].lazy += tot;
        return ;
    }
    down(num);
    update(num << 1, l, r, tot);
    update(num << 1 | 1, l, r, tot);
    a[num].val = a[num << 1].val + a[num << 1 | 1].val;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15