首页 > 代码库 > 线段树 & 题目

线段树 & 题目

首先说下我写的线段树吧。

我是按照线段树【完全版】那个人的写法来写的,因为网上大多数题解都是按照他的写法来写。

确实比较飘逸,所以就借用了。

节点大小是maxn是4倍,准确来说是大于maxn的2^x次方的最小值的两倍。因为要pushUp的时候会去到一些无用的节点。

就是在叶子节点的时候还pushUp了的话,要去到两个无用的节点,所以是最小值的两倍。

lson 和 rson 用宏定义写了。因为是固定的量。

线段树不必保存自身的区间,因为一边传递过去的时候,在函数里就有区间表示,无谓开多些无用的变量。

 

pushUp函数,更新当前节点cur的值,其实就是,线段树一般都是处理完左右孩子,然后再递归更新父亲的嘛,这个pushUp函数就是用来更新父亲的。感觉不用这个函数更加清楚明了。

pushDown函数,在lazy--upDate的时候有用,作用是把延迟标记更新到左右节点。

技术分享
 1 #define lson L, mid, cur << 1 2 #define rson mid + 1, R, cur << 1 | 1 3 void pushUp(int cur) { 4     sum[cur] = sum[cur << 1] + sum[cur << 1 | 1]; 5 } 6 void pushDown(int cur, int total) { 7     if (add[cur]) { 8         add[cur << 1] += add[cur]; //传递去左右孩子 9         add[cur << 1 | 1] += add[cur]; //  val >> 1 相当于 val / 210         sum[cur << 1] += add[cur] * (total - (total >> 1)); //左孩子有多少个节点11         sum[cur << 1 | 1] += add[cur] * (total >> 1); //一共控制11个,则右孩子有5个12         add[cur] = 0;13     }14 }15 void build(int L, int R, int cur) {16     if (L == R) {17         sum[cur] = a[L];18         return;19     }20     int mid = (L + R) >> 1;21     build(lson);22     build(rson);23     pushUp(cur);24 }25 void upDate(int begin, int end, int val, int L, int R, int cur) {26     if (L >= begin && R <= end) {27         add[cur] += val;     28         sum[cur] += val * (R - L + 1);     //这里加了一次,后面pushDown就只能用add[cur]的29         return;30     }31 pushDown(cur, R - L + 1);  //这个是必须的,因为下面的pushUp是直接等于的32 //所以要先把加的,传递去右孩子,然后父亲又调用pushUp,才能保证正确性。33     int mid = (L + R) >> 1; //一直分解的是大区间,开始时是[1, n]这个区间。34     if (begin <= mid) upDate(begin, end, val, lson); //只要区间涉及,就必须更新35     if (end > mid) upDate(begin, end, val, rson);36     pushUp(cur);37 }38 int query(int begin, int end, int L, int R, int cur) {39     if (L >= begin && R <= end) {40         return sum[cur];41     }42     pushDown(cur, R - L + 1);43     int ans = 0, mid = (L + R) >> 1;44     if (begin <= mid) ans += query(begin, end, lson); //只要区间涉及,就必须查询45     if (end > mid) ans += query(begin, end, rson);46     return ans;47 }
成段更新模板

关于成段更新时的upDate函数,中途的pushDown是不能省的,可以看看第三题然后结合我给的数据(数据是poj的大牛发出来的,不是我想的。)关键就在于pushUp函数是直接等于的,你不pushDown,然后pushUp,就会把以前的增加值给抹杀了

HDU 1166    敌兵布阵 

单点更新,区间求和

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

技术分享
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>#define lson L, mid, cur << 1#define rson mid + 1, R, cur << 1 | 1const int maxn = 50000 + 20;int sum[maxn << 2];int a[maxn];void pushUp(int cur) { //更新当前这个节点的信息    sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];}void build(int L, int R, int cur) {    if (L == R) {        sum[cur] = a[L];        return;    }    int mid = (L + R) >> 1;    build(lson);    build(rson);    pushUp(cur);}void upDate(int pos, int val, int L, int R, int cur) {    if (L == pos && R == pos) {        sum[cur] += val;        return;    }    int mid = (L + R) >> 1;    if (pos <= mid) upDate(pos, val, lson);    else            upDate(pos, val, rson);    pushUp(cur);}int query(int begin, int end, int L, int R, int cur) { //[L, R]大区间, [begin, end]查询区间    if (L >= begin && R <= end) { //这个大区间是待查区间的子集        return sum[cur];    }    int mid = (L + R) >> 1;    int ans = 0;    if (begin <= mid) ans += query(begin, end, lson);    if (end > mid)  ans += query(begin, end, rson);    return ans;}int f;void work() {    printf("Case %d:\n", ++f);    int n;    scanf("%d", &n);    for (int i = 1; i <= n; ++i) {        scanf("%d", &a[i]);    }    build(1, n, 1);    char cmd[111];    while (scanf("%s", cmd) != EOF && cmd[0] != E) {        int a, b;        scanf("%d%d", &a, &b);        if (cmd[0] == Q) {            printf("%d\n", query(a, b, 1, n, 1));        } else if (cmd[0] == A) {            upDate(a, b, 1, n, 1);        } else {            upDate(a, -b, 1, n, 1);        }    }    return;}int main() {#ifdef local    freopen("data.txt","r",stdin);#endif    int t;    scanf("%d", &t);    while (t--) {        work();    }    return 0;}
View Code

 

HDU 1754  I Hate It

单点更新,区间最值

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

技术分享
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>#define lson L, mid, cur << 1#define rson mid + 1, R, cur << 1 | 1const int maxn = 200000 + 20;int mx[maxn << 2];int a[maxn];void pushUp(int cur) {    mx[cur] = max(mx[cur << 1], mx[cur << 1 | 1]);}void build(int L, int R, int cur) {    if (L == R) {        mx[cur] = a[L]; //就是自己        return;    }    int mid = (L + R) >> 1;    build(lson);    build(rson);    pushUp(cur);}void upDate(int pos, int val, int L, int R, int cur) {    if (L == pos && R == pos) { //精确到这一个点        mx[cur] = val;        return;    }    int mid = (L + R) >> 1;    if (pos <= mid) upDate(pos, val, lson);    else            upDate(pos, val, rson);    pushUp(cur);}int query(int begin, int end, int L, int R, int cur) {    if (L >= begin && R <= end) {        return mx[cur];    }    int mid = (L + R) >> 1;    int ans = 0;    if (begin <= mid) ans = query(begin, end, lson); //区间有涉及,级要查询    if (end > mid) ans = max(ans, query(begin, end, rson));    return ans;}int n, m;void work() {    for (int i = 1; i <= n; ++i) {        scanf("%d", &a[i]);    }    build(1, n, 1);    for (int i = 1; i <= m; ++i) {        char str[11];        int b, c;        scanf("%s%d%d", str, &b, &c);        if (str[0] == Q) {            printf("%d\n", query(b, c, 1, n, 1));        } else upDate(b, c, 1, n, 1);    }}int main() {#ifdef local    freopen("data.txt","r",stdin);#endif    while (scanf("%d%d", &n, &m) != EOF) {        work();    }    return 0;}
View Code

 

POJ 3468 A Simple Problem with Integers

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

 

成段更新,区间查询总和,这题记得用LL,

给个数据

10 221 2 3 4 5 6 7 8 9 10Q 4 4C 1 10 3C 6 10 3C 6 9 3C 8 9 -100C 7 9 3C 7 10 3C 1 10 3Q 6 10Q 6 9Q 8 9Q 7 9Q 7 10Q 1 10Q 2 4C 3 6 3Q 9 9Q 1 1Q 5 5Q 6 6Q 7 7Q 6 8ans4-82-104-147-122-100-3727-737142125-28
技术分享
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#define lson L, mid, cur << 1#define rson mid + 1, R, cur << 1 | 1const int maxn = 100000 + 20;LL sum[maxn << 2];LL add[maxn << 2];int a[maxn];void pushUp(int cur) {    sum[cur] = sum[cur << 1] + sum[cur << 1 | 1];}void pushDown(int cur, int total) {    if (add[cur]) {        add[cur << 1] += add[cur];        add[cur << 1 | 1] += add[cur]; //  val >> 1 相当于 val / 2        sum[cur << 1] += add[cur] * (total - (total >> 1)); //左孩子有多少个节点        sum[cur << 1 | 1] += add[cur] * (total >> 1); //一共控制11个,则右孩子有5个        add[cur] = 0;    }}void build(int L, int R, int cur) {    if (L == R) {        sum[cur] = a[L];        return;    }    int mid = (L + R) >> 1;    build(lson);    build(rson);    pushUp(cur);}void upDate(int begin, int end, LL val, int L, int R, int cur) {    if (L >= begin && R <= end) {        add[cur] += val;//这里加了一次,后面pushDown就只能用add[cur]的        sum[cur] += val * (R - L + 1); //控制的节点数目        return;    }    pushDown(cur, R - L + 1);    int mid = (L + R) >> 1;    if (begin <= mid) upDate(begin, end, val, lson);    if (end > mid) upDate(begin, end, val, rson);    pushUp(cur);}LL query(int begin, int end, int L, int R, int cur) {    if (L >= begin && R <= end) {        return sum[cur];    }    pushDown(cur, R - L + 1);    LL ans = 0, mid = (L + R) >> 1;    if (begin <= mid) ans += query(begin, end, lson);    if (end > mid) ans += query(begin, end, rson);    return ans;}void work() {    int n, q;    scanf("%d%d", &n, &q);    for (int i = 1; i <= n; ++i) {        scanf("%d", &a[i]);    }    build(1, n, 1);    char str[11];    for (int i = 1; i <= q; ++i) {        scanf("%s", str);        int L, R, val;        if (str[0] == Q) {            scanf("%d%d", &L, &R);            printf("%I64d\n", query(L, R, 1, n, 1));        } else {            scanf("%d%d%d", &L, &R, &val);            upDate(L, R, val, 1, n, 1);        }    }    return;}int main() {#ifdef local    freopen("data.txt","r",stdin);#endif    work();    return 0;}
View Code

 

线段树 & 题目