线段树和树状数组总结

, ,
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

线段树

概念

将[1,n]分解成若干特定的子区间(数量不超过4×n4\times n)
用线段树对“编号连续”的一些点，进行修改或者统计操作，修改和统计的复杂度都是O(log2(n))

用线段树统计的东西，必须符合区间加法，（也就是说，如果已知左右两子树的全部信息，比如要能够推出父节点）；否则，不可能通过分成的子区间来得到[L,R]的统计结果。

一个问题，只要能化成对一些“连续点”的修改和统计问题，基本就可以用线段树来解决了

Lazy思想

对整个结点进行的操作，先在结点上做标记，而并非真正执行，直到根据查询操作的需要分成两部分。

模板

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description: 我也借鉴了好多线段树+lazy的模板，维护值有用数组和结构体的，个人比较喜欢用结构体储存
 然后线段树的操作也就那几种(虽然叫法各异，但是实际上是一样的)：
 建树：build
 更新：update，change，add
 查询：find，query
 标记下放：pushdown
 向上更新：pushup(这个函数就一行，感觉没有必要，即两个子节点向上更新父节点的维护值)
 注意：无论是线段树还是树状数组，初始数组都应该从1开始存数据
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1e5 + 5;

ll a[maxn];
struct node
{
    ll sum;
    ll lazy;
} A[maxn << 2];

void build(int u, int l, int r)
{
    A[u].lazy = 0;
    if (l == r)
    {
        A[u].sum = a[l];//这里可以改为初始数组的
        return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid);
    build(2 * u + 1, mid + 1, r);
    A[u].sum = A[2 * u].sum + A[2 * u + 1].sum;//等价pushup操作
}

//下放操作，将当前的lazy下放
void pushdown(int u, int l,int  r)
{
    if (A[u].lazy == 0)
        return ;
    int mid = (l + r) / 2;
    A[u * 2].sum += A[u].lazy * (mid - l + 1);
    A[u * 2 + 1].sum += A[u].lazy * (r - mid);
    A[u * 2].lazy += A[u].lazy;
    A[u * 2 + 1].lazy += A[u].lazy;
    A[u].lazy = 0;
}

//l,r表示更新区间sl,sr一开始为1, n, u == 1

void add(int u, int sl, int sr, int l, int r, ll k)
{
    if (l > sr || r < sl)
        return ;
    if (l <= sl && r >= sr)
    {
        A[u].sum += k * (sr - sl + 1);
        A[u].lazy += k;
        return ;
    }
    pushdown(u, sl, sr);
    int mid = (sl + sr) / 2;
    add(2 * u, sl, mid, l, r, k);
    add(2 * u + 1, mid + 1, sr, l, r, k);
    A[u].sum = A[u * 2].sum + A[u * 2 + 1].sum;
    return ;
}

ll query(int u, int sl, int sr, int l, int r)
{
    if (l > sr || r < sl)
        return 0;
    if (l <= sl && r >= sr)
        return A[u].sum;
    pushdown(u, sl, sr);
    int mid = (sl + sr) / 2;
    return (query(2 * u, sl, mid, l, r) + query(2 * u + 1, mid + 1, sr, l, r));
}

int t, n, q, x, y, k;
char c;
int main()
{
//    ios::sync_with_stdio(false);
    scanf("%d%d", &n, &q);
//注意：无论是线段树还是树状数组，初始数组都应该从1开始存数据
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build(1, 1, n);
    while (q--)
    {
		scanf(" %c", &c);
        if (c == 'Q')
        {
            scanf("%d %d", &x, &y);
            printf("%lld\n", query(1, 1, n, x, y));
        }
        else
        {
            scanf("%d %d %d", &x, &y ,&k);
            add(1, 1, n, x, y, k);
        }
    }
    return 0;
}

ZKW线段树

重口味？！

其实 zkw 线段树和普通线段树区别没多大（区别可大了去了！）

emmm…起码它们的思想是一致的，都是节点维护区间信息嘛。

只不过…普通线段树的维护和查询是递归式，而 zkw线段树是循环式的

但是不要以为 zkw线段树只是靠循环加速上位的！

zkw线段树能支持非常多强

模板

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1e5 + 5;

int t, n, m, q;

struct node
{
    ll sum;
    int _max, _min, add;
} A[maxn << 2];

ll read()
{
    ll x = 0,f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void build()
{
    for (m = 1; m <= n; m <<= 1);
    for (int i = m + 1; i <= m + n; i++)
        A[i].sum = A[i]._min = A[i]._max = read();
    for (int i = m - 1; i; i--)
    {
        A[i].sum = A[i << 1].sum + A[i << 1 | 1].sum;
        A[i]._min = min(A[i << 1]._min, A[i << 1 | 1]._min);
        A[i << 1]._min -= A[i]._min, A[i << 1 | 1]._min -= A[i]._min;
        A[i]._max = max(A[i << 1]._max, A[i << 1 | 1]._max);
        A[i << 1]._max -= A[i]._max, A[i << 1 | 1]._max -= A[i]._max;
    }
}
//单点更新
void update_node(int x, int v, int a = 0)
{
    x += m, A[x]._max += v, A[x]._min += v, A[x].sum += v;
    for (; x > 1; x >>= 1)
    {
        A[x].sum += v;
        a = min(A[x]._min, A[x ^ 1]._min);
        A[x]._min -= a, A[x ^ 1]._min -= a, A[x >> 1]._min += a;
        a = max(A[x]._max, A[x ^ 1]._max);
        A[x]._max -= a, A[x ^ 1]._max -= a, A[x >> 1]._max += a;
    }
}
//区间更新
void update_part(int s, int t, int v)
{
    int a = 0, lc = 0, rc = 0, len = 1;
    for (s += m - 1, t += m + 1; s ^ t ^ 1; s >>= 1, t >>= 1, len <<= 1)
    {
        if (s & 1 ^  1)
            A[s ^ 1].add += v, lc += len, A[s ^ 1]._min += v, A[s ^ 1]._max += v;
        if (t & 1)
            A[t ^ 1].add += v, rc += len, A[t ^ 1]._min += v, A[t ^ 1]._max += v;
        A[s >> 1].sum += v * lc, A[t >> 1].sum += v * rc;
        a = min(A[s]._min, A[s ^ 1]._min), A[s]._min -= a, A[s ^ 1]._min -= a, A[s >> 1]._min += a;
        a = min(A[t]._min, A[t ^ 1]._min), A[t]._min -= a, A[t ^ 1]._min -= a, A[t >> 1]._min += a;
        a = max(A[s]._max, A[s ^ 1]._max), A[s]._max -= a, A[s ^ 1]._max -= a, A[s >> 1]._max += a;
        a = max(A[t]._max, A[t ^ 1]._max), A[t]._max -= a, A[t ^ 1]._max -= a, A[t >> 1]._max += a;
    }
    for (lc += rc; s; s >>= 1)
    {
        A[s >> 1].sum += v * lc;
        a = min(A[s]._min, A[s ^ 1]._min), A[s]._min -= a, A[s ^ 1]._min -= a, A[s >> 1]._min += a;
        a = max(A[s]._max, A[s ^ 1]._max), A[s]._max -= a, A[s ^ 1]._max -= a, A[s >> 1]._max += a;
    }
}
//单点查询
int query_node(int x,int ans = 0)
{
    for (x += m; x; x >>= 1)
        ans += A[x]._min;
    return ans;
}
//区间查询
ll query_sum(int s, int t)
{
    ll lc = 0, rc = 0, len = 1, ans = 0;
    for (s += m - 1, t += m + 1; s ^ t ^ 1; s >>= 1, t >>= 1, len <<= 1)
    {
        if (s & 1 ^ 1)
            ans += A[s ^ 1].sum + len * A[s ^ 1].add, lc += len;
        if (t & 1)
            ans += A[t ^ 1].sum + len * A[t ^ 1].add, rc += len;
        if (A[s >> 1].add)
            ans += A[s >> 1].add * lc;
        if (A[t >> 1].add)
            ans += A[t >> 1].add * rc;
    }
    for (lc += rc,s >>= 1; s; s >>= 1)
        if (A[s].add)
            ans += A[s].add * lc;
    return ans;
}

int query_min(int s, int t, int L = 0, int R = 0, int ans = 0)
{
    if (s == t)
        return query_node(s);
    for (s += m, t += m; s ^ t ^ 1; s >>= 1, t >>= 1)
    {
        L += A[s]._min, R += A[t]._min;
        if (s & 1 ^ 1)
            L = min(L, A[s ^ 1]._min);
        if (t & 1)
            R = min(R, A[t ^ 1]._min);
    }
    for (ans = min(L, R), s >>= 1; s; s >>= 1)
        ans += A[s]._min;
    return ans;
}

int query_max(int s, int t, int L = 0, int R = 0, int ans = 0)
{
    if (s == t)
        return query_node(s);
    for (s += m, t += m; s ^ t ^ 1; s >>= 1, t >>= 1)
    {
        L += A[s]._max, R += A[t]._max;
        if (s & 1 ^ 1)
            L = max(L, A[s ^ 1]._max);
        if (t & 1)
            R = max(R, A[t ^ 1]._max);
    }
    for (ans = max(L, R), s >>= 1; s; s >>= 1)
        ans += A[s]._max;
    return ans;
}


int main()
{
//    ios::sync_with_stdio(false);
    n = read();
    q = read();
    build();
    int f = 0, x, y, v;
    while (q--)
    {
        f = read();
        if (f == 1)
        {
            x = read();
            y = read();
            v = read();
            update_part(x, y, v);
        }
        else
        {
            x = read();
            y = read();
            printf("%lld\n",query_sum(x, y));
        }
    }
    return 0;
}

####进阶有能力再补
####权值线段树
####主席数
####树套树
###树状数组

####概念

####操作
add();单点更新
getsum();求前缀和
####模板

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
const int maxn=500005;
class TA
{
private:
    int e[maxn];
    int len = maxn;
    int lowbit(int k)
    {
        return k & (-k);
    }
public:
    void add(int x,int v)													//区间更新
    {
        while(x <= len)
            e[x] += v,x += lowbit(x);
    }
    void init(int* getin,int _len)											//初始化
    {
        len = _len;
        for(int i = 1; i <= len; i ++)
            add(i,*(getin + i - 1));
    }
    void init_0()
    {
        len = maxn,memset(e, 0, sizeof(e));
    }
    int getsum(int x)														//询问
    {
        int sum = 0;
        while(x > 0)
            sum += e[x],x -= lowbit(x);
        return sum;
    }
}ta;

题型1单点修改+区间查询

1
2
3
add();

getsum(y) - getsum(x - 1);

题型2区间修改+单点查询

1
2
3
4
先差分
add(x, 1)；
add(y + 1,-1);
getsum();

题型3区间修改 + 区间查询(有树状数组还要什么线段树)

a[1]+a[2]+...+a[x]a[1]+a[2]+...+a[x]
=d[1]+(d[1]+d[2])+(d[1]+d[2]+d[3])+...+(d[1]+d[2]+...+d[x])=d[1]+(d[1]+d[2])+(d[1]+d[2]+d[3])+...+(d[1]+d[2]+...+d[x])
=d[1]×x+d[2]×(x−1)+...+d[x]×1=d[1]\times x+d[2]\times (x-1)+...+d[x]\times 1
=sigma(1<=i<=x)(x−i+1)×d[i]=sigma(1<=i<=x)(x-i+1)\times d[i]
=(sigma(1<=i<=x)d[i])×(x+1)−sigma(1<=i<=x)d[i]×i=(sigma(1<=i<=x)d[i])\times (x+1)-sigma(1<=i<=x)d[i]\times i
因此，可以只在树状数组中记录d[i]的前缀和还有d[i]×id[i]\times i的前缀和
poj3468

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
/*原题中对a[]的区间修改，可以视为对d[]的单点修改，
而s[]又可以由d[i]、i*d[i]的前缀和推导出来。
且维护s1[]、s2[]较容易，因为每次操作都是对d[]进行
单点修改。具体可以参考以下代码*/

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
typedef long long LL;

const int N = 1e5 + 7;

LL s1[N], s2[N];
int n, q;

inline int lowbit(int x)
{
    return x & -x;
}
void add(LL a[], int i, LL x)
{
    while(i <= n)
    {
        a[i] += x;
        i += lowbit(i);
    }
}
LL sum(LL a[], int i)
{
    LL ret = 0;
    while(i)
    {
        ret += a[i];
        i -= lowbit(i);
    }
    return ret;
}
void Add(int i, LL x)
{
    add(s1, i, x * i), add(s2, i, x);
}
LL Sum(int i)
{
    return -sum(s1, i) + (i + 1) * sum(s2, i);
}
int main()
{
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++)
    {
        LL t;
        scanf("%lld", &t);
        Add(i, t), Add(i + 1, -t);
    }
    while(q--)
    {
        int l, r;
        char op[3];
        scanf("%s%d%d", op, &l, &r);
        if(op[0] == 'Q')
            printf("%lld\n", Sum(r) - Sum(l - 1));
        else
        {
            LL t;
            scanf("%lld", &t);
            Add(l, t), Add(r + 1, -t);
        }
    }
}
//2180K 1938MS

//#include<iostream>
//#include<cstdio>
//#include<cstring>
//#include<algorithm>
//#include<queue>
//#include<stack>
//#include<vector>
//#include<map>
//#include<set>
//#include<bitset>
//#include<string>
//#include<cmath>
//#include<sstream>
//using namespace std;
//typedef long long ll;
//const double pi=acos(-1.0);
//const int eps=1e-10;
//const int mod=1e9+7;
//const int INF=0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
//const int maxn=1e5 + 5;
//
//ll c1[maxn];
//ll c2[maxn];
//ll sum[maxn];
//ll n,q;
//ll a[maxn];
//int lowbit(int x)
//{
//    return x & -x;
//}
//
//void add(ll a[], int x, int k)
//{
//    while (x <= n)
//    {
//        a[x] += k;
//        x += lowbit(x);
//    }
//}
//
//ll getsum(ll a[],int x)
//{
//    ll sum = 0;
//    while (x > 0)
//    {
//        sum += a[x];
//        x -= lowbit(x);
//    }
//    return sum;
//}
//
//ll query(int s)
//{
//    return s * getsum(c1, s) - getsum(c2, s);
//}
//
//int main()
//{
//    scanf("%lld%lld", &n, &q);
//    ll temp = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        scanf("%lld", &a[i]);
//        sum[i] = sum[i - 1] + a[i];
//    }
//
//    while (q--)
//    {
//        char c;
//        ll ans = 0;
//        int x, y, v;
//        getchar();
//        c = getchar();
//
//        if (c == 'Q')
//        {
//            scanf("%d%d", &x, &y);
//            ans = sum[y] - sum[x - 1];
//            ans += (y + 1) * getsum(c1, y) - getsum(c2, y);
//            ans -= (x * getsum(c1, x - 1) - getsum(c2, x - 1));
//            printf("%lld\n", ans);
//        }
//        else
//        {
//            scanf("%d%d%d", &x, &y, &v);
//            add(c1, x, v);
//            add(c1, y + 1, -v);
//            add(c2, x, x * v);
//            add(c2, y + 1, -v * (y + 1));
//        }
//    }
//    return 0;
//}
////3736K   1766MS

进阶-二维树状数组

一道模板题

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
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description: 二维树状数组模板
 如果需要区间修改+单点查询，还是可以用差分思想
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1010;

int m;
int num[maxn][maxn];
int treeNum[maxn][maxn];

int lowbit(int x)
{
    return x & (-x);
}
//%d%d*c忽略字符
int getsum(int x, int y)
{
    int sum = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i))
        for(int j = y ; j > 0 ; j -= lowbit(j))
            sum += treeNum[i][j];
    return sum;
}

void add(int x, int y, int val)
{
    for(int i = x ; i < maxn ; i += lowbit(i))
        for(int j = y ; j < maxn ; j += lowbit(j))
            treeNum[i][j] += val;
}
void cf_add(int x, int y, int xx, int yy, int v)
{
    add(x,y,v);
    add(xx+1,yy+1,v);
    add(xx+1,y,-v);
    add(x,yy+1,-v);
}
int query(int x, int y, int xx, int yy)
{
    return getsum(xx, yy) - getsum(xx, y - 1) - getsum(x - 1, yy) + getsum(x - 1, y - 1);
}

int n, x, y, v, xx, yy, q;
char c;
int main()
{
//    ios::sync_with_stdio(false);
    scanf("%d", &n);
    while (n--)
    {
        getchar();
        c = getchar();
        if (c == 'B')
        {
            scanf("%d%d", &x, &y);
            x++, y++;
            if (!num[x][y])
                add(x, y, 1);
            num[x][y] = 1;
        }
        else if (c == 'D')
        {
            scanf("%d%d", &x, &y);
            x++, y++;
            if (num[x][y])
                add(x, y, -1);
            num[x][y] = 0;
        }
        else
        {
            scanf("%d%d%d%d", &x, &xx, &y, &yy);
            x++, y++, xx++, yy++;
            if (x > xx)
                swap(x, xx);
            if (y > yy)
                swap(y, yy);
            printf("%d\n", query(x, y, xx, yy));
        }
    }
    return 0;
}

区间修改+区间查询就跳过吧。。

总结