线段树与树状数组的区别

线段树和树状数组的基本功能都是在某一满足结合律的操作(比如加法，乘法，最大值，最小值)下，O(log⁡n)的时间复杂度内修改单个元素并且维护区间信息。

不同的是，树状数组只能维护前缀“操作和”(前缀和，前缀积，前缀最大最小)，而线段树可以维护区间操作和。但是某些操作是存在逆元的（即：可以用一个操作抵消部分影响，减之于加，除之于乘），这样就给人一种树状数组可以维护区间信息的错觉:维护区间和，模质数意义下的区间乘积，区间 xor 和。能这样做的本质是取右端点的前缀结果，然后对左端点左边的前缀结果的逆元做一次操作，所以树状数组的区间询问其实是在两次前缀和询问。

一个简单的整数问题(树状数组+差分)

题意

给定长度为 N 的数列 A，然后输入 M 行操作指令。

第一类指令形如 C l r d，表示把数列中第 l∼r 个数都加 d。

第二类指令形如 Q x，表示询问数列中第 x 个数的值。

对于每个询问，输出一个整数表示答案。

思考

一般的树状数组：单点加，求区间和

这道题反过来了，用差分数组就行了。

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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 100010;
int n,m;
LL a[N],tr[N];
int lowbit(int x){
    return x&-x;
}

int add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

LL sum(int x){
    LL res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)  cin>>a[i];
    for(int j=1;j<=n;j++) add(j,a[j]-a[j-1]);
    
    char op[3];
    int l,r,d;
    for(int i=1;i<=m;i++){
        scanf("%s",op);
        if(op[0]=='C'){
            cin>>l>>r>>d;
            add(l,d);
            add(r+1,-d);
        }else{
            cin>>l;
            cout<<sum(l)<<endl;
        }
    }
    return 0;
}

谜一样的牛(树状数组+二分)

题意

有 n 头奶牛，已知它们的身高为 1∼n 且各不相同，但不知道每头奶牛的具体身高。

现在这 n 头奶牛站成一列，已知第 i 头牛前面有 Ai 头牛比它低，求每头奶牛的身高。

思考

在本题中，我们首先考虑最后一头牛。由于它已经统计了在它之前的所有牛，因此，假如它比x头牛高，则它的高度一定是x+1。我们采取从后往前考虑的方式，就是因为题目给出了“每头牛已知在自己前面比自己矮的牛的个数”这一条件，从后往前可以少考虑很多问题。

由于每头牛的高度各不相同且取遍区间[1,n]，因此，对于倒数第二头牛而言，它应该在除去上述x+1的区间[1,n]中，选取An−1+1小的数。其他的牛以此类推。

假如建立一个全部元素为1的数列，某个位置的数为1代表这个高度还不知道是哪头牛的，那么就用树状数组维护该数列的前缀和，若某个位置的前缀和等于Ai+1，此时的下标就是要找的数。选择这个数后，将相应位置的1置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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>
#include <unordered_map>

using namespace std;
typedef long long LL;
const int N=100010;

int a[N],tr[N];
int n;

int lowbit(int x){
    return x&-x;
}

int add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

LL sum(int x){
    LL res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
LL ans[N];
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) add(i,1);
    
    for(int i=n;i>=1;i--){
        int k=a[i]+1;
        int l=1,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if(sum(mid)>=k) r=mid;
            else l=mid+1;
        }
        ans[i]=l;
        add(l,-1);
    }
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    
    return 0;
}

一个简单的整数问题2（树状数组+算式推导）

题意

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

  1. C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
  2. Q l r，表示询问数列中第 l∼r 个数的和。

对于每个询问，输出一个整数表示答案。

思考

区间修改+区间查询

因此只需维护两个树状数组即可
一个是差分数组d[i]的树状数组tr[i]，还有一个是i*d[i]的树状数组tri[i]

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
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
typedef long long LL;
int N,M;
LL a[100010];
LL tr[100010];
LL tr2[100010];
int lowbit(int x){
    return x&-x;
}
LL sum(LL tt[],int x){
    LL res=0;
    for(int i=x;i;i-= lowbit(i)) res+=tt[i];
    return res;
}
void add(LL tt[],int x,LL c){
    for(int i=x;i<=N; i+= lowbit(i)) tt[i]+=c;
}
LL get_sum(int x)
{
    return sum(tr, x) * (x + 1) - sum(tr2, x);
}
int main(){
    cin>>N>>M;
    for(int i=1;i<=N;i++) {
        scanf("%lld",&a[i]);
        add(tr,i,a[i]-a[i-1]);
        add(tr2,i,i*(LL)(a[i]-a[i-1]));
    }
    char op[2];
    int l,r,d;
    for(int i=1;i<=M;i++){
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='Q'){
            printf("%lld\n", get_sum(r)- get_sum(l-1));
        }else{
            scanf("%d",&d);

            add(tr, l, d), add(tr2, l, l * d);
            add(tr, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
        }
    }

    return 0;
}

一个简单的整数问题2（线段树板）

结点信息：

Sum: 当前区间的总和

add：懒标记，给以当前节点中的每一个节点，加上add(不包括自己)

记住线段树的五个基本操作

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int w[N];
struct Node
{
    int l, r;
    LL sum, add;
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add)
    {
        left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    }
    else    // 一定要分裂
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}


int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    build(1, 1, n);

    char op[2];
    int l, r, d;

    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C')
        {
            scanf("%d", &d);
            modify(1, l, r, d);
        }
        else printf("%lld\n", query(1, l, r));
    }

    return 0;
}

亚特兰蒂斯(扫描线)

题意

四个数字 $x_{1}, y_{1}, x_{2}, y_{2}$ (不 一定是整数) , $\left(x_{1}, y_{1}\right)$ 和 $\left(x_{2}, y_{2}\right)$ 分别是地图的左上角位置和右下 角位置。

给定很多这样的正方形，求在地图上覆盖的面积

思路

代码

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 100010;

int n;
struct Segment
{
    double x, y1, y2;
    int k;
    bool operator< (const Segment &t)const
    {
        return x < t.x;
    }
}seg[N * 2];
struct Node
{
    int l, r;
    int cnt;
    double len;
}tr[N * 8];

vector<double> ys;

int find(double y)
{
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void pushup(int u)
{
    if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else if (tr[u].l != tr[u].r)
    {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    }
    else tr[u].len = 0;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l != r)
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += k;
        pushup(u);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

int main()
{
    int T = 1;
    while (scanf("%d", &n), n)
    {
        ys.clear();
        for (int i = 0, j = 0; i < n; i ++ )
        {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            seg[j ++ ] = {x1, y1, y2, 1};
            seg[j ++ ] = {x2, y1, y2, -1};
            ys.push_back(y1), ys.push_back(y2);
        }

        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        build(1, 0, ys.size() - 2);

        sort(seg, seg + n * 2);

        double res = 0;
        for (int i = 0; i < n * 2; i ++ )
        {
            if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
        }

        printf("Test case #%d\n", T ++ );
        printf("Total explored area: %.2lf\n\n", res);
    }

    return 0;
}