首页 > 代码库 > 线段树·题解报告

线段树·题解报告

                                                  线段树·题解报告

参考资料

·课件

线段树 --刘汝佳 

统计的力量,线段树全接触 --张昆玮

·Blog

【完全版】线段树

从普通线段树到zkw线段树

[总结][数据结构]ZKW线段树详解 

 

选题目录

· Hdu1166 敌兵布阵(单点更新,区间求和) 

· Hdu1754 I Hate It(单点更新,RMQ)

· Hdu3308 LCIS(单点更新,区间并) 

· Poj3468 A Simple Problem with Integers(区间加减,区间求和)

· Poj2777 Count Color(区间修改,区间查询,染色) 

 

线段树总结

普通版递归线段树:


  

每层都是[a,b]的划分L=b-a, 则共log2L

任两个结点要么是包含关系要么没有公共部分不可能部分重叠

给定一个叶子p, 从根到p路径上所有结点(p的所有直系祖先)代表的区间都包含点p, 且其他结点代表的区间都不包含点p

给定一个区间[l, r], 可以把它分解为不超过2log2L条不相交线段的并

Lazy思想记录有哪些指令而不真正执行它们等到需要计算的时候再说

根据题目要求确定维护信息和附加信息

具有解决问题的通用性

 

 

II zkw线段树:

 

堆式存储,好写,效率较高

自底向上,非递归更新和查询

Lazy标记

 

 

题解报告              

                      题目1:Hdu1166 敌兵布阵

 

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1166

 

题目大意

有N个正整数,对其进行三种操作:

Add   i, j                    第i个数增加j

Sub   i, j    第i个数减去j

Query i, j                    查询区间[i, j]中数的和

Input

第一行一个整数T,表示有T组数据。

每组数据第一行一个正整数N(N<=50000),接下来有N个整数。

接下来每行有一条命令,命令有4种形式:

Add   i, j                    第i个数增加j

Sub   i, j    第i个数减去j

Query i, j                    查询区间[i, j]中数的和

End   表示结束

每组数据最多有40000条命令

Output

对第i组数据, 首先输出Case i:和回车,

对于每个Query询问,输出一个整数并回车,表示询问的区间中数的总和,这个数不超过1000000.

 

思路

线段树的单点修改,区间求和,可以用zkw线段树维护区间和,提高效率,并便于编写代码.

 

算法步骤

1. 建树

存储空间: T[4 * N], 初始化为0

M:                        M = 1; while (M < n + 2) M <<= 1;

T[M+1]T[M+n]:          n个输入的整数

T[M-1]T[1]:    T[i] = T[2*i] + T[2*i+1];  

2. 更新x

更新最下层的数T[x+M], 并自底向上更新其父结点的值

T[i] = T[2*i] + T[2*i+1]; 

  3. 查询[l,r]

令闭区间[l,r]变成(l-1,r+1).

自底向上查询(l = l-1+M, r = r+1+m)开始查询如果l

是树中左结点(~l & 1)则加上其右端点值;

如果r是树中右结点(r & 1)则加上其左端点值;

向上查询: l >>= 1; r >>= 1;

lr是同层兄弟时结束(l ^ r ^ 1)

 

算法复杂度

建树O(n), 查询和修改O(logn)

总时间复杂度: O(Alogn)                     (A为总操作数)

总空间复杂度: O(4 * n)

 

源程序

/*

 * Author:    HongSheng Zeng

 * Email:     zenghsh3@gmail.com

 * FileName:  1166.cpp

 * Creation:  2014/08/31

 */

#include <iostream>

#include <cstdio>

#include <string>

#include <string.h>

using namespace std;

 

const int N = 50000 + 10;

int n, M, i;

int T[4 * N];

 

void BuildTree()

{

        memset(T, 0, sizeof(T));

        M = 1;

        while (M < n + 2)

                M <<= 1;

        for (i = M + 1; i <= M + n; ++i) 

                scanf("%d", &T[i]);

        for (i = M - 1; i; --i)

                T[i] = T[2 * i] + T[2 * i + 1];

}

 

int Query(int l, int r)

{

        l += M - 1; r += M + 1;

        int ans = 0;

        while (l ^ r ^ 1) {

                if (~l & 1) ans += T[l + 1];

                if (r & 1) ans += T[r - 1];

                l >>= 1; r >>= 1;

        }

        return ans;

}

 

void update(int x, int k)

{

        x += M;

        T[x] += k;

        while (x > 1) {

                x >>= 1;

                T[x] = T[2 * x] + T[2 * x + 1];

        }

}

 

int main()

{

        int t, l, r, x, value;

        char ch[10];

        scanf("%d", &t);

        for (int i = 1; i <= t; ++i) {

                scanf("%d", &n);

                BuildTree();

                printf("Case %d:\n", i);

                while (scanf("%s", ch)) {

                        string s = string(ch);

                        if (s == "End")

                                break;

                        if (s == "Query") {

                                scanf("%d%d", &l, &r);

                                printf("%d\n", Query(l, r));

                        }

                        if (s == "Add") {

                                scanf("%d%d", &x, &value);

                                update(x, value);

                        }

                        if (s == "Sub") {

                                scanf("%d%d", &x, &value);

                                update(x, -value);

                        }

                }

        }

}

 

评测系统上运行结果

Accepted. 运行时间 312ms, 占用内存1128KB.

 

 

 

 

                      题目2:Hdu1754 I Hate It 

 

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1754

 

题目大意

老师需要询问从某某到某某当中,分数最高的是多少,也需要更新某位同学的成绩.

Input

题目包含多组测试,处理到文件结束。 

在每个测试的第一行,有两个正整数 N  M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。 

学生ID编号分别从1编到N。 

第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。 

接下来有M行。每一行有一个字符 C (只取‘Q‘或‘U‘) ,和两个正整数A,B。 

当C为‘Q‘的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。 

当C为‘U‘的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。 

Output

对于每一次询问操作,在一行里面输出最高成绩。

 

思路

线段树的单点修改,区间求最值(RMQ),可以用zkw线段树维护区间最值,提高效率,并便于编写代码.

 

算法步骤

 1.建树

存储空间: T[4 * N], 初始化为0

M:                        M = 1; while (M < n + 2) M <<= 1;

T[M+1]T[M+n]:          n个输入的整数

T[M-1]T[1]:    T[i] = max(T[2*i], T[2*i+1]);  

 2.更新x

更新最下层的数T[x+M], 并自底向上更新其父结点的值

T[i] = max(T[2*i], T[2*i+1]);

 3. 查询[l,r]

令闭区间[l,r]变成(l-1,r+1).

自底向上查询(l = l-1+M, r = r+1+m)开始查询.

Int ans = 0;

如果l是树中左结点(~l & 1)且其右端点值大于ans,ans等于其右端点值;

如果r是树中右结点(r & 1)且其左端点值大于ans,ans等于其左端点值;

向上查询:  l >>= 1; r >>= 1;

lr是同层兄弟时结束(l ^ r ^ 1)

 

算法复杂度

建树O(n), 查询和修改O(logn)

总时间复杂度: O(Alogn)                     (A为总操作数)

总空间复杂度: O(4 * n)

 

源程序

/*

 * Author:    HongSheng Zeng

 * Email:     zenghsh3@gmail.com

 * FileName:  1754.cpp

 * Creation:  2014/09/01

 */

#include <iostream>

#include <cstdio>

#include <string.h>

using namespace std;

 

const int N = 200000 + 10;

int n, m, M, l, r, x, k;

int T[4 * N];

 

void Build_Tree()

{

        memset(T, 0, sizeof(T));

        M = 1;

        while (M < n + 2) 

                M <<= 1;

        for (int i = M + 1; i <= M + n; ++i)

                scanf("%d", &T[i]);

        for (int i = M - 1; i; --i)

                T[i] = max(T[i * 2], T[i * 2 + 1]);

}

 

void Update()

{

        x += M;

        T[x] = k;

        while (x) {

                x >>= 1;

                T[x] = max(T[x * 2], T[x * 2 + 1]);

        }

}

 

int Query()

{

        l += M - 1; r += M + 1;

        int ans = 0;

        while (l ^ r ^ 1) {

                if (~l & 1) 

                        ans = max(ans, T[l + 1]);

                if (r & 1)

                        ans = max(ans, T[r - 1]);

                l >>= 1; r >>= 1;

        }

        return ans;

}

 

int main()

{

        while (scanf("%d%d", &n, &m) != EOF) {

                Build_Tree();

                char ch;

                while (m--) {

                        scanf(" %c", &ch);

                        if (ch == ‘Q‘) {

                                scanf("%d%d", &l, &r);

                                printf("%d\n", Query());

                        }

                        else {

                                scanf("%d%d", &x, &k);

                                Update();

                        }

                }

        }

}

 

评测系统上运行结果

Accepted. 运行时间 953ms, 占用内存3448KB.

 

 

 

 

 

                     题目3:Hdu3308 敌兵布阵 

 

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=3308

 

题目大意

给出一个长度为N(N <= 100000)的数列,然后是两种操作:
U A B: 将第A个数替换为B (下标从零开始)
Q A B: 输出区间[A, B]的最长连续递增子序列
询问的次数m <= 100000。

Input

第一行一个整数T,表示有T组数据。

每组数据第一行有一个整数n和m(0<n,m<=105),接下来有n个整数(0<=val<=105);

接下来m行,每行有一条命令,命令有2种形式:

U A B    (用B替换第A个数, 下标从0开始计数)

Q A B   (查询区间[A, B]中最长连续子序列的长度) 

Output

对于每个Q操作,输出结果.

 

思路

线段树的单点修改,求区间并(查询区间的最长连续子序列)

Case1: 父节点的左儿子右端点值 >= 父节点的右儿子左端点值

父节点维护区间中的最长连续子序列=max(左儿子最长连续子序列,右儿子最长连续子序列)

 

Case2: 父节点的左儿子右端点值 父节点的右儿子左端点值 

父节点维护区间中的最长连续子序列=max(左儿子最长连续子序列,右儿子最长连续子序列,左儿子维护区间中以其右端点结束的最长连续子序列+右儿子维护区间中以其左端点开始的最长连续子序列)

故线段树中需要维护区间的最长连续子序列(smax),区间以左端点开始的最长连续子序列(lmax),和区间以右端点结束的最长连续子序列(rmax).维护信息较复杂且查询时自顶向下比较方便,故用普通版的递归线段树.

算法步骤

0. 信息向上更新

通过Up操作(详见源代码)将父节点的左右儿子的smaxlmaxrmax信息更新到父节点。

1.建树

struct node 

{

        int l, r, lmax, rmax, smax;

} tree[3 * N];  

从上往下建树,然后从下往上更新维护信息.

2.更新x

从上往下,确定x,并更新其值,然后通过Up操作往上更新维护信息。 

3. 查询[l,r]

从上往下递归查询区间,跨区间时需合并结果。

 

算法复杂度

建树O(n), 查询和修改O(logn)

总时间复杂度: O(Alogn)                     (A为总操作数)

总空间复杂度: O(3 * n)

源程序

/*

 * Author:    HongSheng Zeng

 * Email:     zenghsh3@gmail.com

 * FileName:  3308.cpp

 * Creation:  2014/09/10

 */

#include <iostream>

#include <cstdio>

#include <string.h>

using namespace std;

 

const int  N = 100000 + 10;

int num[N];

 

struct node 

{

        int l, r, lmax, rmax, smax;

} tree[3 * N];

 

void Up(int x)

{

        int l = tree[x].l, r = tree[x].r;

        int mid = (l + r) / 2;

        tree[x].lmax = tree[x * 2].lmax;

        tree[x].rmax = tree[x * 2 + 1].rmax;

        tree[x].smax = max(tree[x * 2].smax, tree[x * 2 + 1].smax);

        if (num[mid] < num[mid + 1]) {

                if (tree[x].lmax == (mid - l + 1))

                        tree[x].lmax += tree[x * 2 + 1].lmax;

                if (tree[x].rmax == (r - mid))

                        tree[x].rmax += tree[x * 2].rmax;

                tree[x].smax = max(tree[x].smax, tree[x * 2].rmax + tree[x * 2 + 1].lmax);

        }

}

 

void BuildTree(int x, int l, int r) 

{

        tree[x].l = l;

        tree[x].r = r;

        if (l == r) {

                tree[x].lmax = tree[x].rmax = tree[x].smax = 1;

                return;

        }

        int mid = (l + r) / 2;

        BuildTree(x * 2, l, mid);

        BuildTree(x * 2 + 1, mid + 1, r);

        Up(x);

}

 

void Update(int x, int k)

{

        if (tree[x].l == tree[x].r) 

                return;

        int l = tree[x].l , r = tree[x].r;

        int mid = (l + r) / 2;

        if (k <= mid)

                Update(x * 2, k);

        else 

                Update(x * 2 + 1, k);

        Up(x);

}

 

int Query(int x, int l, int r) 

{

        if (tree[x].l == l && tree[x].r == r)

                return tree[x].smax;

        int mid = (tree[x].l + tree[x].r) / 2;

        if (r <= mid)

                return Query(x * 2, l, r);

        else if (l > mid)

                return Query(x * 2 + 1, l, r);

        else {

                int ans = max(Query(x * 2, l, mid), Query(x * 2 + 1, mid + 1, r));

                if (num[mid] < num[mid + 1]) {

                        ans = max(ans, min(tree[x * 2].rmax, mid - l +1) + 

                                        min(tree[x * 2 + 1].lmax, r - mid));

                }

                return ans;

        }

}

                

int main()

{

        int t, l, r, index, k, n, m;

        char ch;

        scanf("%d", &t);

        while (t--) {

                scanf("%d%d", &n, &m);

                for (int i = 1; i <= n; ++i)

                        scanf("%d", &num[i]);

                BuildTree(1, 1, n);

                while (m--) {

                        scanf(" %c", &ch);

                        if (ch == ‘Q‘) {

                                scanf("%d%d", &l, &r);

                                ++l; ++r;

                                printf("%d\n", Query(1, l, r));

                        }

                        else {

                                scanf("%d%d", &index, &k);

                                ++index;

                                num[index] = k;

                                Update(1, index);

                        }

                }

        }

}

 

评测系统上运行结果

Accepted. 运行时间 484ms, 占用内存5832KB.

 

 

 

 

           题目4:Poj3468 A Simple Problem with Integers 

 

题目链接

http://poj.org/problem?id=3468

 

题目大意

有N个正整数,对其进行两种操作:

‘Q a b ’     询问a~b这段数的和

‘C a b c’    把a~b这段数都加上c

Input

第一行两个整数N,Q, 1 ≤ N,Q ≤ 100000.

接下来有N个整数:A1, A2, ... , AN,  -1000000000 ≤ Ai ≤ 1000000000.

接下来有Q行,每行有一条命令,命令有2种形式:

"C a b c"     Aa, Aa+1, ... , Ab 的值都加上c,  -10000 ≤ c ≤ 10000.
"Q a b"      查询区间Aa, Aa+1, ... , Ab的值的总和.

Output

对于每个Query询问,输出一个数并回车,表示询问的区间中数的总和.

思路

线段树的区间加,区间求和,使用线段树+lazy标记,因为只需要维护区间和,从下往上也可以便利地查询,所以用zkw线段树。

算法步骤

1. 建树

存储空间: T[4 * N], 初始化为0

标记空间: mark[4 * N], 初始化为0, mark[i]表示i结点以下所有结点更新值之和,mark[i]不为0 时说明结点i的更新信息还没更新到其子结点.

M:                        M = 1; while (M < n + 2) M <<= 1;

h:                        树的高度

T[M+1]T[M+n]:          n个输入的整数

T[M-1]T[1]:    T[i] = T[2*i] + T[2*i+1];  

  2. down(x)操作

 标记下传沿着根结点到x的线路,父结点的标记信息更新到其子结点,并清空父结点的标记    信息.

  3. up(x)操作

沿着x到根结点的路线,用子结点的维护信息更新父结点的维护信息.

  4.更新[l, r], +k

l += M - 1; r += M + 1;

标记下传down(l), down(r);

lazy更新结点:

如果l是树中左结点(~l & 1)则更新其右端点值+k,并更新其标记值+k;

如果r是树中右结点(r & 1)则更新其左端点值+k,并更新其标记值+k;

向上更新: l >>= 1; r >>= 1;

lr是同层兄弟时结束(l ^ r ^ 1)

       对l父结点和r父结点进行up操作

  5. 查询[l,r]

l += M - 1; r += M + 1;

标记下传down(l), down(r)

查询:

如果l是树中左结点(~l & 1)则加上其右端点值;

如果r是树中右结点(r & 1)则加上其左端点值;

向上查询: l >>= 1; r >>= 1;

lr是同层兄弟时结束(l ^ r ^ 1)

 

算法复杂度

建树O(n), 查询和修改O(logn)

总时间复杂度: O(Alogn)                     (A为总操作数)

总空间复杂度: O(4 * n)

源程序

/*

 * Author:    HongSheng Zeng

 * Email:     zenghsh3@gmail.com

 * FileName:  3468.cpp

 * Creation:  2014/09/03

 */

#include <iostream>

#include <cstdio>

#include <string.h>

using namespace std;

 

const int N = 100000 + 10;

int n, q, M, h, l , r, ll, rr, t;

long long k;

long long T[4 * N];

long long mark[4 * N];

 

void Build_Tree()

{

        memset(T, 0, sizeof(T));

        memset(mark, 0, sizeof(mark));

 

        int i;

        M = 1; h = 0;

        while (M < n + 2) {

                M <<= 1;

                ++h;

        }

        for (i = M + 1; i <= M + n; ++i) 

                scanf("%lld", &T[i]);

        for (i = M - 1; i; --i)

                T[i] = T[i * 2] + T[2 * i + 1];

}

 

void down(int x)

{

        for (int i = h; i; --i) 

                if (mark[t = x >> i]) {

                        mark[t] >>= 1;

                        mark[t << 1] += mark[t]; mark[t * 2 + 1] += mark[t];

                        T[t << 1] += mark[t]; T[t * 2 + 1] += mark[t];

                        mark[t] = 0;

                }

}

 

void up(int x)

{

        while (x) {

                T[x] = T[x << 1] + T[x * 2 + 1];

                x >>= 1;

        }

}

 

void Update()

{

        l += M -1; r += M + 1;

        ll = l >> 1; rr = r >> 1;

        down(l); down(r);

        while (l ^ r ^ 1) {

                if (~l & 1) {

                        T[l + 1] += k;

                        mark[l + 1] += k;

                }

                if (r & 1) {

                        T[r - 1] += k;

                        mark[r - 1] += k;

                }

                k <<= 1;

                l >>= 1; r >>= 1;

        }

        up(ll); up(rr);

}

        

long long Query()

{

        long long ans = 0;

        l += M - 1; r += M + 1;

        down(l); down(r);

        while (l ^ r ^ 1) {

                if (~l & 1) ans += T[l + 1];

                if (r & 1) ans += T[r - 1];

                l >>= 1; r >>= 1;

        }

        return ans;

}

 

int main()

{

        scanf("%d%d", &n, &q);

        Build_Tree();

        char ch;

        for (int i = 0; i < q; ++i) {

                scanf(" %c%d%d", &ch, &l, &r);

                if (ch == ‘Q‘) {

                        printf("%lld\n", Query());

                } else {

                        scanf("%lld", &k);

                        Update();

                }

        }

}

评测系统上运行结果

Accepted. 运行时间 2219ms, 占用内存6952KB.

 

 

 

                            题目5:Poj2777 Count Color

 

题目链接

http://poj.org/problem?id=2777

 

题目大意

有一个区间[1,L],被分成L段,标记为1,2...L;最多有T种颜色。有两种操作,一种是对某一个区间段染上某一种颜色,一种是询问该区间有多少种不同的颜色。整个区间刚开始为1.

Input

第一行L (1 <= L <= 100000), T (1 <= T <= 30) 和 O (1 <= O <= 100000). 

接下来O行,每行有一条命令,命令有2种形式:

C A B C     (给A到B区间染上C色)

Q A B      (查询区间[A, B]有多少种不同的颜色) 

Output

对于每个Q操作,输出结果.

 

思路

线段树的染色问题,区间修改,区间查询.

结点维护信息: 0-非纯色; 非0-纯颜色当结点为非纯色时,才需要访问其子结点查询

自上向下查询比较方便,用普通版递归线段树.

 

算法步骤

1.建树

struct node

{

        int l, r, color;

} tree[3 * N]; 

从上往下建树,颜色初始化为1.

2.更新[l, r]

区间颜色标记下放,从上往下lazy更新. 

3. 查询[l,r]

从上往下递归查询,当结点为非纯色时,才向下查询其子结点

 

算法复杂度

建树O(n), 查询和修改O(logn)

总时间复杂度: O(Alogn)                     (A为总操作数)

总空间复杂度: O(3 * n)

源程序

/*

 * Author:    HongSheng Zeng

 * Email:     zenghsh3@gmail.com

 * FileName:  2777.cpp

 * Creation:  2014/09/07

 */

#include <iostream>

#include <cstdio>

#include <string.h>

using namespace std;

 

const int N = 100000 + 10;

 

struct node

{

        int l, r, color;

} tree[3 * N];

 

bool mark[35];

 

void Build_Tree(int x, int l, int r)

{

        tree[x].l = l;

        tree[x].r = r;

        tree[x].color = 1;

        if (l == r)

                return;

        int mid = (l + r) / 2;

        Build_Tree(x * 2, l, mid);

        Build_Tree(x * 2 + 1, mid + 1, r);

}

 

void Update(int x, int l, int r, int color)

{

        if (tree[x].l == l && tree[x].r == r) {

                tree[x].color = color;

                return;

        }

 

        // Down 

        

        if (tree[x].color != 0 && tree[x].color != color) {

                tree[x * 2].color = tree[x].color;

                tree[x * 2 + 1].color = tree[x].color;

                tree[x].color = 0;

        }

 

        int mid = (tree[x].l + tree[x].r) / 2;

        if (r <= mid)

                Update(x * 2, l, r, color);

        else if (l > mid)

                Update(x * 2 + 1, l, r, color);

        else  {

                Update(x * 2, l, mid, color);

                Update(x * 2 + 1, mid + 1, r, color);

        }

}

 

void Query(int x, int l, int r)

        if (tree[x].color > 0) {

                mark[tree[x].color] = true;

                return;

        }

        int mid = (tree[x].l + tree[x].r) / 2;

        if (r <= mid)

                Query(x * 2, l, r);

        else if (l > mid)

                Query(x * 2 + 1, l, r);

        else {

                Query(x * 2, l, mid);

                Query(x * 2 + 1, mid + 1, r);

        }

}

int main()

{

        int L, T, O, l, r, k;

        char ch;

        scanf("%d%d%d", &L, &T, &O);

        memset(mark, false, sizeof(mark));

        Build_Tree(1, 1, L);

        while (O--) {

              scanf(" %c%d%d", &ch, &l, &r);

              if (l > r) {

                      l = l ^ r;

                      r = l ^ r;

                      l = l ^ r;

              }

              if (ch == ‘C‘) {

                      scanf("%d", &k);

                      Update(1, l, r, k);

              }

              else {

                       memset(mark, false, sizeof(mark));

                       Query(1, l, r);

                       int sum = 0;

                       for (int i = 1; i <= T; ++i)

                               if (mark[i])

                                       ++sum;

                       printf("%d\n", sum);

              }

        }

}

 

评测系统上运行结果

Accepted. 运行时间 422ms, 占用内存3764KB.


线段树·题解报告