created by Dejavu
(不斷更新中)

• 概念

線段樹唾那，類似區(qū)間樹觉壶，是一個(gè)完全二叉樹官觅，它在各個(gè)節(jié)點(diǎn)保存一條線段（數(shù)組中的一段子數(shù)組）孩等，主要用于高效解決連續(xù)區(qū)間的動(dòng)態(tài)查詢問題，由于二叉結(jié)構(gòu)的特性署海，它基本能保持每個(gè)操作的復(fù)雜度為O(lgN)吗购，你可以在數(shù)據(jù)結(jié)構(gòu)可視(visualgo)網(wǎng)站中看到算法的具體搭建過程。

• c++ 模板代碼

這里的代碼是對(duì)區(qū)間寫入優(yōu)化后的代碼砸狞，加入了lazy_tag用來標(biāo)記區(qū)間更新的位置

//最好不要用頭文件bits/stdc++.h 因?yàn)橐恍┚幾g器會(huì)不支持這個(gè)頭文件

#include <iostream>
using namespace std;
#define MaxN 50005
class SegTree {
public:
    int left, right;
    int sum;
    int lazy_tag;
    int mid() { return (left + right) >> 1; }
};
SegTree tree[MaxN];
void pushUp(int rt) { tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum; }
void pushDown(int rt, int len) {
    int tag = tree[rt].lazy_tag;
    if (tag) {
        tree[rt << 1].lazy_tag += tag;
        tree[rt << 1 | 1].lazy_tag += tag;
        tree[rt << 1].sum += tag*(len - (len >> 1));
        tree[rt << 1 | 1].sum += tag*(len >> 1);
        tree[rt].lazy_tag = 0;
    }
}
void build(int rt, int left, int right) {
    tree[rt].left = left;
    tree[rt].right = right;
    tree[rt].lazy_tag = 0;
    if (left == right) { cin >> tree[rt].sum;return; }
    int mid = tree[rt].mid();
    build(rt << 1, left, mid);
    build(rt << 1 | 1, mid + 1, right);
    pushUp(rt);
}
void update(int rt, int val, int left, int right) {
    if (tree[rt].left == left && tree[rt].right == right) {
        tree[rt].lazy_tag += val;
        tree[rt].sum += val*(right - left + 1);
        return;
    }
    if (tree[rt].left == tree[rt].right) return;
    pushDown(rt, tree[rt].right - tree[rt].left + 1);
    int mid = tree[rt].mid();
    if (right <= mid) update(rt << 1, val, left, right);
    else if (left > mid) update(rt << 1 | 1, val, left, right);
    else {
        update(rt << 1, val, left, mid);
        update(rt << 1 | 1, val, mid + 1, right);
    }
    pushUp(rt);
}
int query(int rt, int left, int right) {
    if (tree[rt].left == left && tree[rt].right == right) return tree[rt].sum;
    pushDown(rt, tree[rt].right - tree[rt].left + 1);
    int mid = tree[rt].mid();
    int sum(0);
    if (right <= mid) sum += query(rt << 1, left, right);
    else if (left > mid) sum += query(rt << 1 | 1, left, right);
    else {
        sum += query(rt << 1, left, mid);
        sum += query(rt << 1 | 1, mid + 1, right);
    }
    return sum;
}
int main() {
    ios::sync_with_stdio(false);
    int n;cin >> n;
    build(1, 1, n);
    char cmd;
    int in1, in2, val;
    while (cin >> cmd, cmd != 'E') {
        if (cmd == 'Q') { cin >> in1 >> in2;cout << query(1, in1, in2) << endl; }
        if (cmd == 'A') { cin >> in1 >> in2 >> val;update(1, val, in1, in2); }
    }
}

例題

• 單點(diǎn)更新
  最最基礎(chǔ)的線段樹,只更新葉子節(jié)點(diǎn),然后把信息用pushUP(int rt)這個(gè)函數(shù)更新上來
• hdu1166 敵兵布陣
• hdu1754 I Hate It
• hdu1394 Minimum Inversion Number
• hdu2795 Billboard
• poj2828 Buy Tickets
• poj2886 Who Gets the Most Candies?
• 成段更新
  需要用到延遲標(biāo)記(或者說懶惰標(biāo)記),簡單來說就是每次更新的時(shí)候不要更新到底,用延遲標(biāo)記使得更新延遲到下次需要更新or詢問到的時(shí)候
• hdu1698 Just a Hook
• poj3468 A Simple Problem with Integers
• poj2528 Mayor’s posters
• poj3225 Help with Intervals
• poj1436 Horizontally Visible Segments
• 區(qū)間合并
  這類題目會(huì)詢問區(qū)間中滿足條件的連續(xù)最長區(qū)間,所以pushUp的時(shí)候需要對(duì)左右兒子的區(qū)間進(jìn)行合并
• poj2991 Crane
• hdu3308 LCIS
• hdu3397 Sequence operation
• hdu2871 Memory Control
• hdu1540 Tunnel Warfare
• CF46-D Parking Lot
• 掃描線
  這類題目需要將一些操作排序,然后從左到右用一根掃描線(當(dāng)然是在我們腦子里)掃過去
  最典型的就是矩形面積并,周長并等題
• hdu1542 Atlantis
• hdu1828 Picture
• hdu3265 Posters
• hdu3642 Get The Treasury
• poj2482 Stars in Your Window
• poj2464 Brownie Points II
• hdu3255 Farming
• ural1707 Hypnotoad’s Secret
• uva11983 Weird Advertisement

題解和代碼性能分析

• 單點(diǎn)更新
  • hdu1166 敵兵布陣
    求區(qū)間和

//c++ 用類似c的方法寫
#include <stdio.h>
#include <string.h>
#define MaxN 50000
int t[MaxN * 4];
inline void pushUp(int rt) { t[rt] = t[rt << 1] + t[rt << 1 | 1]; }
void build(int rt,int l,int r) {
    if (l == r) {scanf("%d",&t[rt]);return;}
    int m = (l + r) >> 1;
    build(rt << 1, l, m);
    build(rt << 1 | 1, m + 1, r);
    pushUp(rt);
}
void update(int rt, int l, int r, int p, int v) {
    if (l == r) { t[rt] += v;return; }
    int m = (l + r) >> 1;
    if (p <= m) update(rt << 1, l, m, p, v);
    else update(rt << 1 | 1, m + 1, r, p, v);
    pushUp(rt);
}
int query(int rt,int l,int r, int _l, int _r) {
    if (_l <= l && r <= _r) return t[rt];
    int m = (l + r) >> 1;
    int sum(0);
    if (_r <= m) sum += query(rt << 1, l, m, _l, _r);
    else if (_l > m) sum += query(rt << 1 | 1, m + 1, r, _l, _r);
    else {
        sum += query(rt << 1, l, m, _l, _r);
        sum += query(rt << 1 | 1, m + 1, r, _l, _r);
    }
    return sum;
}
void main() {
    int n, tn;scanf("%d",&n);tn = n;
    while (tn--) {
        int num;scanf("%d", &num);
        build(1, 1, num);
        printf("Case %d:\n", n - tn);
        char cmd[10];
        int in1, in2;
        while (scanf("%s", &cmd)) {
            if (cmd[0] == 'E') break;
            scanf("%d%d", &in1, &in2);
            if (cmd[0] == 'A') update(1, 1, num, in1, in2);
            else if (cmd[0] == 'S') update(1, 1, num, in1, -in2);
            else printf("%d\n", query(1, 1, num, in1, in2));
            memset(cmd, '\0', sizeof(cmd));
        }
    }
}

上面代碼在hdu運(yùn)行的結(jié)果

//更改query函數(shù)
int sum(0);
void query(int rt, int l, int r, int _l, int _r) {
    if (_l <= l && r <= _r) {sum += t[rt];return;}
    int m = (l + r) >> 1;
    if (_r <= m) query(rt << 1, l, m, _l, _r);
    else if (_l > m) query(rt << 1 | 1, m + 1, r, _l, _r);
    else {
        query(rt << 1, l, m, _l, _r);
        query(rt << 1 | 1, m + 1, r, _l, _r);
    }
}

更改query函數(shù)將sum作為全局變量

//c++ 用c寫法下捻勉，全宏定義
#include <stdio.h>
#include <string.h>
#define MaxN 50000
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define mid int m=(l+r)>>1
#define base int rt,int l,int r
#define we_base 1,1,num
int t[MaxN*4];
inline void pushUp(int rt) { t[rt] = t[rt << 1] + t[rt << 1 | 1]; }
void build(base) {
    if (l == r) { scanf("%d", &t[rt]);return; }
    mid;
    build(lson);
    build(rson);
    pushUp(rt);
}
void update(base, int p, int v) {
    if (l == r) { t[rt] += v;return; }
    mid;
    if (p <= m) update(lson, p, v);
    else update(rson, p, v);
    pushUp(rt);
}
int query(base, int _l, int _r) {
    if (_l <= l && r <= _r) return t[rt];
    mid;
    int sum(0);
    if (_r <= m) sum += query(lson, _l, _r);
    else if (_l > m) sum += query(rson, _l, _r);
    else {
        sum += query(lson, _l, _r);
        sum += query(rson, _l, _r);
    }
    return sum;
}
void main() {
    int n, tn;scanf("%d", &n);tn = n;
    while (tn--) {
        int num;scanf("%d", &num);
        build(we_base);
        printf("Case %d:\n", n - tn);
        char cmd[10];
        int in1, in2;
        while (scanf("%s", &cmd)) {
            if (cmd[0] == 'E') break;
            scanf("%d%d", &in1, &in2);
            if (cmd[0] == 'A') update(we_base, in1, in2);
            else if (cmd[0] == 'S') update(we_base, in1, -in2);
            else printf("%d\n", query(we_base, in1, in2));
            memset(cmd, '\0', sizeof(cmd));
        }
    }
}

c寫法全宏定義

可見使用宏定義的算法運(yùn)行速度比普通寫法稍快一些，而且寫代碼的速度將會(huì)比普通寫法快

//用c++的形式寫
#include <iostream>
#include <string>
using namespace std;
#define MaxN 50000
int t[MaxN * 4];
inline void pushUp(int rt) { t[rt] = t[rt << 1] + t[rt << 1 | 1]; }
void build(int rt,int l,int r) {
    if (l == r) { cin >> t[rt];return; }
    int m = (l + r) >> 1;
    build(rt << 1, l, m);
    build(rt << 1 | 1, m + 1, r);
    pushUp(rt);
}
void update(int rt, int l, int r, int p, int v) {
    if (l == r) { t[rt] += v;return; }
    int m = (l + r) >> 1;
    if (p <= m) update(rt << 1, l, m, p, v);
    else update(rt << 1 | 1, m + 1, r, p, v);
    pushUp(rt);
}
int query(int rt,int l,int r, int _l, int _r) {
    if (_l <= l && r <= _r) return t[rt];
    int m = (l + r) >> 1;
    int sum(0);
    if (_r <= m) sum += query(rt << 1, l, m, _l, _r);
    else if (_l > m) sum += query(rt << 1 | 1, m + 1, r, _l, _r);
    else {
        sum += query(rt << 1, l, m, _l, _r);
        sum += query(rt << 1 | 1, m + 1, r, _l, _r);
    }
    return sum;
}
void main() {
    ios::sync_with_stdio(false);
    int n, tn;cin >> n;tn = n;
    while (tn--) {
        int num;cin >> num;
        build(1, 1, num);
        cout << "Case " << n - tn <<":" << endl;
        string cmd;
        int in1, in2;
        while (cin >> cmd, cmd != "End") {
            cin>> in1 >> in2;
            if (cmd == "Add") update(1, 1, num, in1, in2);
            else if (cmd == "Sub") update(1, 1, num, in1, -in2);
            else cout << query(1, 1, num, in1, in2) << endl;
        }
    }
}

ios::sync_with_stdio(false)

ios::sync_with_stdio(true)

這里的1000ms并不是真正的運(yùn)行時(shí)間而是超時(shí)后就停止運(yùn)行了刀森，就是說當(dāng)設(shè)置為true時(shí)踱启，運(yùn)行時(shí)間是遠(yuǎn)遠(yuǎn)超過設(shè)置為false時(shí)的時(shí)間的，sync_with_stdio(bool)這個(gè)語句是詢問是否與stdio庫同步，同步過程會(huì)耗費(fèi)很多時(shí)間

//c++ 下全宏定義寫法
#include <iostream>
#include <string>
using namespace std;
#define MaxN 50000
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define mid int m=(l+r)>>1
#define base int rt,int l,int r
#define we_base 1,1,num
int t[MaxN*4];
inline void pushUp(int rt) { t[rt] = t[rt << 1] + t[rt << 1 | 1]; }
void build(base) {
    if (l == r) { cin >> t[rt];return; }
    mid;
    build(lson);
    build(rson);
    pushUp(rt);
}
void update(base, int p, int v) {
    if (l == r) { t[rt] += v;return; }
    mid;
    if (p <= m) update(lson, p, v);
    else update(rson, p, v);
    pushUp(rt);
}
int query(base, int _l, int _r) {
    if (_l <= l && r <= _r) return t[rt];
    mid;
    int sum(0);
    if (_r <= m) sum += query(lson, _l, _r);
    else if (_l > m) sum += query(rson, _l, _r);
    else {
        sum += query(lson, _l, _r);
        sum += query(rson, _l, _r);
    }
    return sum;
}
void main() {
    ios::sync_with_stdio(false);
    int n, tn;cin >> n;tn = n;
    while (tn--) {
        int num;cin >> num;
        build(we_base);
        cout << "Case " << n - tn << ":" << endl;
        string cmd;
        int in1, in2;
        while (cin >> cmd, cmd != "End") {
            cin >> in1 >> in2;
            if (cmd == "Add") update(we_base, in1, in2);
            else if (cmd == "Sub") update(we_base, in1, -in2);
            else cout << query(we_base, in1, in2) << endl;
        }
    }
}

c++ 下全宏定義寫法

然而使用c++下的頭文件和空間名埠偿，似乎用宏定義效果并不好

代碼運(yùn)行各項(xiàng)性能對(duì)比

c寫法

c++下普通c的寫法

更改query函數(shù)將sum作為全局變量

c寫法全宏定義

c++寫法

ios::sync_with_stdio(false)

ios::sync_with_stdio(true)

c++ 下全宏定義寫法

用c++的輸入輸出流在性能上會(huì)比c的輸入輸出流慢一些透罢，即使加了去同步語句，所以acm的代碼最好采用c的輸入輸出流

• hdu1754 I Hate It
  求區(qū)間最大值

#include <cstdio>
#define s scanf
#define p printf
#define base int rt,int l,int r
#define we_base 1,1,num
#define max(v1,v2) v1>v2?v1:v2
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define mid int m=(l+r)>>1
#define MaxN 200000
int t[MaxN * 4];
inline void pushUp(int rt) { t[rt] = max(t[rt << 1], t[rt << 1 | 1]); }
void build(base) {
    if (l == r) s("%d", &t[rt]);
    else {
        mid;
        build(lson);
        build(rson);
        pushUp(rt);
    }
}
void update(base, int pos, int v) {
    if (l == r) t[rt] = v;
    else {
        mid;
        if (pos <= m) update(lson, pos, v);
        else update(rson, pos, v);
        pushUp(rt);
    }
}
int query(base, int _l, int _r) {
    if (_l <= l&&_r >= r) return t[rt];
    mid;
    if (_r <= m) return query(lson, _l, _r);
    else if (_l > m) return query(rson, _l, _r);
    else {
        int t1 = query(lson, _l, m);
        int t2 = query(rson, m + 1, _r);
        return max(t1, t2);
    }
    }
}
void main() {
    int num, m;
    while (s("%d%d", &num, &m) != EOF) {
        build(we_base);
        char cmd;
        int in1, in2;
        while (m--) {
            s("\n%c%d%d", &cmd, &in1, &in2);
            if (cmd == 'U') update(we_base, in1, in2);
            else p("%d\n", query(we_base, in1, in2));
        }
    }
}