ACM線分樹、樹状配列入門問題(コード説明付き)

37119 ワード
データ構造 線分樹 ツリー配列
初心者の方なら、このブログを見てください.よく書けています.
目次
HDU 1166敵兵布陣(線分樹)
HDU 1698 Just a Hook(線分樹)
POJ 3468 A Simple Problem with Integers(線分樹区間修正＋加算)
HDU 1540 Tunnel Warfare(最長連続区間＋単点修正)
洛谷P 372【テンプレート】線分樹1
洛谷P 373【テンプレート】線分樹2
洛谷P 198[JSOI 2008]最大数(線分樹またはRMQ)
洛谷P 531 I Hate It(線分樹または樹状配列)
2018年全国多校アルゴリズム冬休みトレーニングキャンプ練習試合(第五場)逆序数(樹状配列)
2018年全国多校アルゴリズム冬休みトレーニングキャンプ練習試合(第5回)H Tree Recovery(線分樹)
パワーoj 2821:Y先輩のGCD難題(線分樹区間は最大公因数＋区間修正を求める)
区間(interval)(牛客白月戦5)(差動)
POJ 2299 Ultra-QuickSort(樹状配列は逆序数を求める)
HU 4000 Fuit Ninja(樹状配列)
POJ 2481 Cows(ツリー配列)
POJ 1990 MooFest(樹状配列)
POJ 3264 Balanced Lineup(RMQ)
HDU 1166敵兵布陣(線分樹)
問題:線分樹のテンプレートの問題ですが、木の形の配列を使うのはもっと簡単です.ここの前の木の配列のコードです.後ろのは線分樹のコードです.
ツリー配列:
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 5e4 + 1000;
const int mod = 1e9 + 7;
const int inf = 1e9;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int bit[maxn];

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

void update(int x, int c) {
    while (x < maxn) {
        bit[x] += c;
        x += lowbit(x);
    }
}

int qeroy(int x) {
    int sum = 0;
    while (x) {
        sum += bit[x];
        x -= lowbit(x);
    }
    return sum;
}

int main() {
    int t;
    cin >> t;
    for (int tt = 1; tt <= t; tt++) {
        cout << "Case " << tt << ":" << endl;
        me(bit, 0);
        char s[10];
        int n, a, b, x;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            update(i, x);
        }
        while (scanf("%s", s) != EOF) {
            if (s[0] == 'E')
                break;
            scanf("%d%d", &a, &b);
            if (s[0] == 'Q')
                printf("%d
", qeroy(b) - qeroy(a - 1));
            else if (s[0] == 'A')
                update(a, b);
            else
                update(a, -b);
        }
    }
    return 0;
}
線分樹:
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 5e4 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int sum[maxn << 2];

void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", &sum[rt]);
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

int num(int L, int R, int l, int r, int rt) {
    if (l >= L && R >= r)
        return sum[rt];
    int m = (l + r) >> 1;
    int s = 0;
    if (L <= m)
        s += num(L, R, l, m, rt << 1);
    if (R > m)
        s += num(L, R, m + 1, r, rt << 1 | 1);
    return s;
}

void update(int s, int c, int l, int r, int rt) {
    if (l == r) {
        sum[rt] += c;
        return;
    }
    int m = (l + r) >> 1;
    if (s <= m)
        update(s, c, l, m, rt << 1);
    else
        update(s, c, m + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

int main() {
    int t;
    cin >> t;
    for (int tt = 1; tt <= t; tt++) {
        cout << "Case " << tt << ":" << endl;
        me(sum, 0);
        int n;
        string s;
        scanf("%d", &n);
        build(1, n, 1);
        while (cin >> s) {
            if (s == "End")
                break;
            int a, b;
            scanf("%d%d", &a, &b);
            if (s == "Query")
                printf("%d
", num(a, b, 1, n, 1));
            else if (s == "Add")
                update(a, b, 1, n, 1);
            else
                update(a, -b, 1, n, 1);
        }
    }
    return 0;
}
 
HDU 1698 Just a Hook(線分樹)
この問題は問題を見ても分かります.とても裸の段樹の区間修正の問題です.
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
typedef long long ll;
using namespace std;
int num[maxn << 2], add[maxn << 2];

void up_data(int rt) {
    num[rt] = num[rt << 1] + num[rt << 1 | 1];
}

void build(int l, int r, int rt) {
    if (l == r) {
        num[rt] = 1;
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    up_data(rt);
}

void push_down(int rt, int l, int r) {
    if (add[rt]) {
        int m = (l + r) >> 1;
        num[rt << 1] = (m - l + 1) * add[rt];
        num[rt << 1 | 1] = (r - m) * add[rt];
        add[rt << 1] = add[rt << 1 | 1] = add[rt];
        add[rt] = 0;
    }
}

void push_data(int x, int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r) {
        num[rt] = (r - l + 1) * x;
        add[rt] = x;
        return;
    }
    push_down(rt, l, r);
    int m = (l + r) >> 1;
    if (L <= m)
        push_data(x, L, R, l, m, rt << 1);
    if (R > m)
        push_data(x, L, R, m + 1, r, rt << 1 | 1);
    up_data(rt);
}

int main() {
    int t, Case = 1;
    cin >> t;
    while (t--) {
        me(num, 0), me(add, 0);
        int n, m;
        cin >> n;
        build(1, n, 1);
        cin >> m;
        while (m--) {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            push_data(x, l, r, 1, n, 1);
        }
        cout << "Case " << Case++ << ": The total value of the hook is " << num[1] << "." << endl;
    }
    return 0;
}
 
POJ 3468 A Simple Problem with Integers(線分樹区間修正＋加算)
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
ll num[maxn << 2], add[maxn << 2];

void pushup(int rt) {
    num[rt] = num[rt << 1] + num[rt << 1 | 1];
}

void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%lld", &num[rt]);
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    pushup(rt);
}

void updata(int l, int r, int rt) {
    if (add[rt]) {
        int m = (l + r) >> 1;
        add[rt << 1] += add[rt];
        add[rt << 1 | 1] += add[rt];
        num[rt << 1] += add[rt] * (m - l + 1);
        num[rt << 1 | 1] += add[rt] * (r - m);
        add[rt] = 0;
    }
}

void pushdata(int L, int R, int c, int l, int r, int rt) {
    if (L <= l && R >= r) {
        num[rt] += (r - l + 1) * c, add[rt] += c;
        return;
    }
    int m = (l + r) >> 1;
    updata(l, r, rt);
    if (L <= m)
        pushdata(L, R, c, l, m, rt << 1);
    if (R > m)
        pushdata(L, R, c, m + 1, r, rt << 1 | 1);
    pushup(rt);
}

ll getsum(int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r)
        return num[rt];
    ll sum = 0;
    updata(l, r, rt);
    int m = (l + r) >> 1;
    if (L <= m)
        sum += getsum(L, R, l, m, rt << 1);
    if (R > m)
        sum += getsum(L, R, m + 1, r, rt << 1 | 1);
    return sum;
}

int main() {
    int m, n;
    while (cin >> n >> m) {
        me(num, 0), me(add, 0);
        build(1, n, 1);
        while (m--) {
            char s[5];
            scanf("%s", s);
            if (s[0] == 'Q') {
                int x, y;
                scanf("%d%d", &x, &y);
                cout << getsum(x, y, 1, n, 1) << endl;
            } else {
                int x, y, c;
                scanf("%d%d%d", &x, &y, &c);
                pushdata(x, y, c, 1, n, 1);
            }
        }
    }
    return 0;
}
 
HDU 1540 Tunnel Warfare(最長連続区間＋単点修正) 
件名:
操作一:ある村は壊滅された.
操作の2:1つの村の座標を与えて、この村を含む最長の未被村の長さを求めます.
操作三:最後に破壊された村が修復されます.
最初に、私たちは線分樹で最長の連続区間の長さを維持することを考えられます.今は1の代表的な変更点で破壊されず、0で改点が破壊されたことを表しています.そして、前回の破壊点をスタックまたは配列でセットします.そして線分樹メンテナンス1の最長長さです.  
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 5e4 + 5;
const int mod = 10007;
const int inf = 1e9;
const long long onf = 1e18;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI 3.14159265358979323846
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int ls[maxn << 2], rs[maxn << 2], sum[maxn << 2];
///sum          ，ls              ，rs   r      
int n, m;

void push_up(int l, int r, int rt) {
    int mid = (l + r) >> 1;
    ls[rt] = ls[rt << 1];
    if (ls[rt << 1] == mid - l + 1)///                ，                       
        ls[rt] += ls[rt << 1 | 1];
    rs[rt] = rs[rt << 1 | 1];
    if (rs[rt << 1 | 1] == r - mid)///       
        rs[rt] += rs[rt << 1];
    sum[rt] = max(ls[rt], rs[rt]);
    sum[rt] = max(sum[rt], max(sum[rt << 1], sum[rt << 1 | 1]));
    sum[rt] = max(sum[rt], rs[rt << 1] + ls[rt << 1 | 1]);
    ///          ，   ，         ，         +             。（                 ）
}

void build(int l, int r, int rt) {
    if (l == r) {
        ls[rt] = rs[rt] = sum[rt] = 1;///            
        return;
    }
    int mid = (l + r) >> 1;
    build(lson);
    build(rson);
    push_up(l, r, rt);
}

void push_date(int pos, int x, int l, int r, int rt) {
    sum[rt] = ls[rt] = rs[rt] = 0;
    if (l == r) {
        sum[rt] = ls[rt] = rs[rt] = x;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        push_date(pos, x, lson);
    else
        push_date(pos, x, rson);
    push_up(l, r, rt);
}

int query(int pos, int l, int r, int rt) {
    if (l == r)
        return sum[rt];
    int mid = (l + r) >> 1;
    if (pos <= mid) {///        
        if (pos >= mid - rs[rt << 1] + 1)
            return ls[rt << 1 | 1] + rs[rt << 1];///               ，                   +        （                     ）
        else
            return query(pos, lson);///           ，                 ，        
    } else {
        if (pos <= mid + ls[rt << 1 | 1])///       
            return ls[rt << 1 | 1] + rs[rt << 1];
        else
            return query(pos, rson);
    }
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        build(1, n, 1);
        stack q;
        while (m--) {
            char str[2];
            int x;
            scanf("%s", str);
            if (str[0] == 'D') {
                scanf("%d", &x);
                push_date(x, 0, 1, n, 1);
                q.push(x);
            } else if (str[0] == 'Q') {
                scanf("%d", &x);
                printf("%d
", query(x, 1, n, 1));
            } else {
                if (q.size()) {
                    push_date(q.top(), 1, 1, n, 1);
                    q.pop();
                }
            }
        }
    }
    return 0;
}
 
洛谷P 372【テンプレート】線分樹1
裸の線分樹.
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
ll sum[maxn << 2], add[maxn << 2];

void updata(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void lazy(int l, int r, int rt) {
    if (add[rt]) {
        int m = (l + r) >> 1;
        sum[rt << 1] += (m - l + 1) * add[rt];
        sum[rt << 1 | 1] += (r - m) * add[rt];
        add[rt << 1] += add[rt];
        add[rt << 1 | 1] += add[rt];
        add[rt] = 0;
    }
}

void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%lld", &sum[rt]);
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    updata(rt);
}

void pushdata(int L, int R, int x, int l, int r, int rt) {
    if (L <= l && R >= r) {
        sum[rt] += (r - l + 1) * x;
        add[rt] += x;
        return;
    }
    lazy(l, r, rt);
    int m = (l + r) >> 1;
    if (L <= m)
        pushdata(L, R, x, l, m, rt << 1);
    if (R > m)
        pushdata(L, R, x, m + 1, r, rt << 1 | 1);
    updata(rt);
}

ll getsum(int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r)
        return sum[rt];
    lazy(l, r, rt);
    int m = (l + r) >> 1;
    ll s = 0;
    if (L <= m)
        s += getsum(L, R, l, m, rt << 1);
    if (R > m)
        s += getsum(L, R, m + 1, r, rt << 1 | 1);
    return s;
}

int main() {
    int n, m;
    cin >> n >> m;
    build(1, n, 1);
    while (m--) {
        int a, x, y, k;
        scanf("%d", &a);
        if (a == 1) {
            scanf("%d%d%d", &x, &y, &k);
            pushdata(x, y, k, 1, n, 1);
        } else {
            scanf("%d%d", &x, &y);
            printf("%lld
", getsum(x, y, 1, n, 1));
        }
    }
    return 0;
}
 
洛谷P 373【テンプレート】線分樹2
まだ線分樹の裸問題ですが、区間修正の時、彼は一つの数に乗ります.この時、怠け者マークを下に置いて、下に付ける怠け者マークと乗りたい怠け者マークを下に置くのです.
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
typedef long long ll;
using namespace std;
ll num[maxn << 2], add[maxn << 2], ch[maxn << 2];
ll n, m, p;

void init(int n) {
    for (int i = 1; i <= 4 * n; i++)
        num[i] = add[i] = 0, ch[i] = 1;
}

void updata(int rt) {
    num[rt] = (num[rt << 1] + num[rt << 1 | 1]) % p;
}

void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%lld", &num[rt]);
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    updata(rt);
}

void push_down(int l, int r, int rt) {
    int m = (l + r) >> 1;
    add[rt << 1] = (add[rt << 1] * ch[rt] + add[rt]) % p;
    add[rt << 1 | 1] = (add[rt << 1 | 1] * ch[rt] + add[rt]) % p;
    ch[rt << 1] = (ch[rt << 1] * ch[rt]) % p;
    ch[rt << 1 | 1] = (ch[rt << 1 | 1] * ch[rt]) % p;
    num[rt << 1] = (num[rt << 1] * ch[rt] + (m - l + 1) * add[rt]) % p;
    num[rt << 1 | 1] = (num[rt << 1 | 1] * ch[rt] + (r - m) * add[rt]) % p;
    ch[rt] = 1, add[rt] = 0;
}

void push_data(int flog, int x, int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r) {
        if (flog == 1) {
            add[rt] = (add[rt] * x) % p;
            ch[rt] = (ch[rt] * x) % p;
            num[rt] = (num[rt] * x) % p;
        } else {
            add[rt] = (add[rt] + x) % p;
            num[rt] = (num[rt] + (r - l + 1) * x) % p;
        }
        return;
    }
    int m = (l + r) >> 1;
    push_down(l, r, rt);
    if (L <= m)
        push_data(flog, x, L, R, l, m, rt << 1);
    if (R > m)
        push_data(flog, x, L, R, m + 1, r, rt << 1 | 1);
    updata(rt);
}

ll get_sum(int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r)
        return num[rt];
    int m = (l + r) >> 1;
    push_down(l, r, rt);
    ll s = 0;
    if (L <= m)
        s = (s + get_sum(L, R, l, m, rt << 1)) % p;
    if (R > m)
        s = (s + get_sum(L, R, m + 1, r, rt << 1 | 1)) % p;
    return s % p;
}

int main() {
    cin >> n >> m >> p;
    init(n);
    build(1, n, 1);
    while (m--) {
        int flog, x, y, k;
        scanf("%d", &flog);
        if (flog == 3) {
            scanf("%d%d", &x, &y);
            printf("%lld
", get_sum(x, y, 1, n, 1));
        } else {
            scanf("%d%d%d", &x, &y, &k);
            push_data(flog, k, x, y, 1, n, 1);
        }
    }
    return 0;
}
 
洛谷P 198[JSOI 2008]最大数(線分樹またはRMQ)
これは裸の線分樹とRMQの問題です.ここでこの二つのコードを貼り付けます.
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int ma[maxn][21], a[maxn];

void RMQ(int u) {
    ma[u][0] = a[u];
    for (int i = 1; (1 << i) <= u; i++)
        ma[u][i] = max(ma[u][i - 1], ma[u - (1 << (i - 1))][i - 1]);
}

int getmax(int l, int r) {
    int x = log(r - l + 1.0) / log(2.0);
    return max(ma[l][x], ma[l + (1 << x) - 1][x]);
}

int main() {
    int n, d;
    cin >> n >> d;
    int l = 0, t = 0;
    while (n--) {
        char str[5];
        scanf("%s", str);
        if (str[0] == 'A') {
            int x;
            scanf("%d", &x);
            a[++l] = (x + t) % d;
            RMQ(l);
        } else {
            int x;
            scanf("%d", &x);
            int ans = getmax(l - x + 1, l);
            printf("%d
", ans);
            t = ans;
        }
    }
    return 0;
}
線分樹:
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 2e5 + 10;
const int mod = 1e9;
const int inf = 1e9;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int ma[maxn << 2];

void updata(int rt) {
    ma[rt] = max(ma[rt << 1], ma[rt << 1 | 1]);
}

void build(int l, int r, int rt) {
    if (l == r) {
        ma[rt] = -inf;
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
}

void charu(int c, int x, int l, int r, int rt) {
    if (l == r) {
        ma[rt] = x;
        return;
    }
    int m = (l + r) >> 1;
    if (c <= m)
        charu(c, x, l, m, rt << 1);
    else
        charu(c, x, m + 1, r, rt << 1 | 1);
    updata(rt);
}

int getmax(int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r)
        return ma[rt];
    int m = (l + r) >> 1;
    int temp = -2147283647;
    if (L <= m)
        temp = max(temp, getmax(L, R, l, m, rt << 1));
    if (R > m)
        temp = max(temp, getmax(L, R, m + 1, r, rt << 1 | 1));
    return temp;
}

int main() {
    int n, d, temp = 0, l = 0;
    cin >> n >> d;
    build(1, maxn, 1);
    while (n--) {
        char str[5];
        scanf("%s", str);
        if (str[0] == 'A') {
            int x;
            scanf("%d", &x);
            l++;
            charu(l, (x + temp) % d, 1, maxn, 1);
        } else {
            int x;
            scanf("%d", &x);
            temp = getmax(l - x + 1, l, 1, maxn, 1);
            printf("%d
", temp);
        }
    }
    return 0;
}
 
洛谷P 531 I Hate It(線分樹または樹状配列)
裸の線分樹.
線分樹:
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int ma[maxn << 2];

void updata(int rt) {
    ma[rt] = max(ma[rt << 1], ma[rt << 1 | 1]);
}

void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", &ma[rt]);
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    updata(rt);
}

void pushdata(int c, int x, int l, int r, int rt) {
    if (l == r) {
        if (ma[rt] < x)
            ma[rt] = x;
        return;
    }
    int m = (l + r) >> 1;
    if (c <= m)
        pushdata(c, x, l, m, rt << 1);
    else
        pushdata(c, x, m + 1, r, rt << 1 | 1);
    updata(rt);
}

int getmax(int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r)
        return ma[rt];
    int m = (l + r) >> 1;
    int ma1 = 0, ma2 = 0;
    if (L <= m)
        ma1 = getmax(L, R, l, m, rt << 1);
    if (R > m)
        ma2 = getmax(L, R, m + 1, r, rt << 1 | 1);
    return max(ma1, ma2);
}

int main() {
    int n, m;
    cin >> n >> m;
    me(ma, 0);
    build(1, n, 1);
    while (m--) {
        char str[2];
        int a, b;
        scanf("%s%d%d", str, &a, &b);
        if (str[0] == 'Q')
            printf("%d
", getmax(a, b, 1, n, 1));
        else
            pushdata(a, b, 1, n, 1);
    }
    return 0;
}
 
2018年全国多校アルゴリズム冬休みトレーニングキャンプ練習試合(第五場)逆序数(樹状配列)
注:裸の配列ツリーは逆の順序を求めるので、行列を宣言して、現在の位置よりも大きな数を記録します.逆の順序数は、ちょうど前に出てくるのが後ろより大きい数です.前に1つの数を入力すると、彼より小さい数の配列をプラスします.最後に直接的に配列の数をプラスすると、前の入力数よりも大きい数の数です.
#include 
#include
#include
#include
#include
#include
#include
#include

const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int bit[maxn], n;

struct node {
    int x, i;

    bool friend operator
 
2018年全国多校アルゴリズム冬休みトレーニングキャンプ練習試合(第5回)H Tree Recovery(線分樹)
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int num[maxn << 2], add[maxn << 2];

void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", &num[rt]);
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    num[rt] = num[rt << 1] + num[rt << 1 | 1];
}

void pushdown(int ln, int rn, int rt) {
    if (add[rt]) {
        add[rt << 1] += add[rt];
        add[rt << 1 | 1] += add[rt];
        num[rt << 1] += add[rt] * ln;
        num[rt << 1 | 1] += add[rt] * rn;
        add[rt] = 0;
    }
}

void updata(int L, int R, int c, int l, int r, int rt) {
    if (L <= l && R >= r) {
        num[rt] += (r - l + 1) * c;
        add[rt] += c;
        return;
    }
    int m = (l + r) >> 1;
    pushdown(m - l + 1, r - m, rt);
    if (L <= m)
        updata(L, R, c, l, m, rt << 1);
    if (R > m)
        updata(L, R, c, m + 1, r, rt << 1 | 1);
    num[rt] = num[rt << 1] + num[rt << 1 | 1];
}

int query(int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r)
        return num[rt];
    int s = 0;
    int m = (l + r) >> 1;
    pushdown(m - l + 1, r - m, rt);
    if (L <= m)
        s += query(L, R, l, m, rt << 1);
    if (R > m)
        s += query(L, R, m + 1, r, rt << 1 | 1);
    return s;
}

int main() {
    int n, m;
    cin >> n >> m;
    build(1, n, 1);
    while (m--) {
        string s;
        int a, b, c;
        cin >> s;
        if (s == "Q") {
            scanf("%d%d", &a, &b);
            cout << query(a, b, 1, n, 1) << endl;
        } else {
            scanf("%d%d%d", &a, &b, &c);
            updata(a, b, c, 1, n, 1);
        }
    }
    return 0;
}
 
パワーoj 2821:Y先輩のGCD難題(線分樹区間は最大公因数＋区間修正を求める)
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int d[maxn << 2], lazy[maxn << 2];

int gcd(int a, int b) {
    if (!b)
        return a;
    return gcd(b, a % b);
}

void update(int rt) {
    d[rt] = gcd(d[rt << 1], d[rt << 1 | 1]);
}

void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", &d[rt]);
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    update(rt);
}

void pushdown(int rt) {
    if (lazy[rt]) {
        d[rt << 1] = d[rt << 1 | 1] = lazy[rt];
        lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];
        lazy[rt] = 0;
    }
}

void pushdate(int L, int R, int c, int l, int r, int rt) {
    if (L <= l && R >= r) {
        d[rt] = lazy[rt] = c;
        return;
    }
    pushdown(rt);
    int m = (l + r) >> 1;
    if (L <= m)
        pushdate(L, R, c, l, m, rt << 1);
    if (R > m)
        pushdate(L, R, c, m + 1, r, rt << 1 | 1);
    update(rt);
}

int getgcd(int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r)
        return d[rt];
    pushdown(rt);
    int m = (l + r) >> 1;
    int a = 0, b = 0;
    if (L <= m)
        a = getgcd(L, R, l, m, rt << 1);
    if (R > m)
        b = getgcd(L, R, m + 1, r, rt << 1 | 1);
    return gcd(a, b);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        me(d, 0), me(lazy, 0);
        build(1, n, 1);
        while (q--) {
            int x, a, b, c;
            scanf("%d", &x);
            if (x == 1) {
                scanf("%d%d%d", &a, &b, &c);
                pushdate(min(a, b), max(a, b), c, 1, n, 1);
            } else {
                scanf("%d%d", &a, &b);
                printf("%d
", getgcd(min(a, b), max(a, b), 1, n, 1));
            }
        }
    }
    return 0;
}
 
区間(interval)(牛客白月戦5)(差動)
線分樹で作ってもいいですが、それはちょっと面倒です.ここでは差分を使って、このように更新するしかないです.境界ノードです.具体的な思想はコードを見て理解できます.
#include 
#include
#include
#include
#include
#include
#include
#include

const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9;
#define me(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
ll num[maxn], a[maxn];

int main() {
    int n, m;
    while (cin >> n >> m) {
        me(num);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            num[i] = a[i] - a[i - 1];
        }
        while (m--) {
            int q, l, r, p;
            scanf("%d%d%d%d", &q, &l, &r, &p);
            if (q == 1) {
                num[l] -= p;
                num[r + 1] += p;
            } else {
                num[l] += p;
                num[r + 1] -= p;
            }
        }
        for (int i = 1; i <= n; i++)
            a[i] = a[i - 1] + num[i];
        int x, y;
        cin >> x >> y;
        ll sum = 0;
        for (int i = x; i <= y; i++)
            sum += a[i];
        cout << sum << endl;
    }
    return 0;
}
 
POJ 2299 Ultra-QuickSort(樹状配列は逆序数を求める)
前にもう似たような問題がありましたが、はっきり言っていません.ここで話したのは比較的詳しいです.
これは離散化が必要です.
一つの構造体を作ってvalとidを含んで、valは入力の数で、idは入力の順序を表します.その後、valによって小さい時から大きい順に並べられます.もしvalが等しいなら、idによって並べられます.逆順がないなら、IDはiと同じであり、逆序数があるなら、iとidは違っています.したがって、ツリー配列の特性を利用して、逆数の個数を簡単に算出することができます.
まだ分からないなら例を挙げます.(4個の数を入力)
入力:9-1 18 5
出力3.
入力したら対応する構造体がこうなります.
val:9-1 18
id: 1 2 3 4
順番を決めてからになります.
val: -1 5 9 18
id:     2 4 1 3
2 4 1 3の逆序数も3です.
その後、樹状配列の特性を利用すれば問題を解決できます.
数字が重複している可能性があるので、追加操作は単に1ではなく、＋＋＋である.
#include 
#include
#include
#include
#include
#include
#include
#include

const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int bit[maxn], n;

struct node {
    int x, i;

    bool friend operator
 
HU 4000 Fuit Ninja(樹状配列)
n個の数を与えて、すべてのiを求める.
問題は最後の数を二番目に大きくすることです.i番目の数字aを入力すると、私たちが使っている樹状配列はsum(a-1)であり、sum(a-1)はaという位置を表しています.i-1個の数のうち、sum(a-1)個の数はaより小さいので、後の(i+1,n)のシーケンスの中で、R=(n-a)-(i-1-sum(a-1)の数よりも大きいです.(a-1)個の数がaより大きいとR=(n-a)-(i-1-sum(a-1)は後の数がaより大きいということを示します.そして、aは3つの数の中の最小値として考えて、それらを組み合わせると、C(R,2)つまりR*(R-1)があるのではないかと思います.2、後のシーケンスは固定されているので、順序付けの概念はなく、つまり、元のシーケンスは5、4の場合を考える必要はありません.4、5の場合は固定されていますので、後のシーケンスはRから2つを選択すればいいです.そして、C(R、2)はすべてのa＋2つの大きさを表します.(つまり、小・中・大・中は全部中に含まれています)ので、私達が要求するのは小・中です.だから、aごとに小・中・大の場合を差し引いて、小・中・大＝sum(a−1)＊Rとなります.だから、最後の答えは(1,n)の全部の数に対して、SUM(C(R,2)-sum(a−1)＊Rとなります.
#include 
#include
#include
#include
#include
#include
#include
#include

const int maxn = 5e5 + 5;
const int mod = 1e8 + 7;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int n, bit[maxn];

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

void updata(int x) {
    while (x <= n) {
        bit[x]++;
        x += lowbit(x);
    }
}

int getsum(int x) {
    int s = 0;
    while (x) {
        s += bit[x];
        x -= lowbit(x);
    }
    return s;
}

int main() {
    int t, Case = 0;
    cin >> t;
    while (t--) {
        me(bit, 0);
        scanf("%d", &n);
        ll sum = 0, x, l, r;///l,     x      ，r       x      。
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            updata(x);
            l = getsum(x - 1);
            r = (n - x) - (i - l - 1);///(n-x)         x ，(i-1-l)   i-1     sum(x-1)   a 
            sum += r * (r - 1) / 2 - r * l;
        }
        printf("Case #%d: %lld
", ++Case, sum % mod);
    }
    return 0;
}
 
POJ 2481 Cows(ツリー配列)
先に意味を書きます.つまり、いくつかの線分を入力します.この線分は最大何本かの線分If Si(=Sj and Ej<=Ei and Ei-Si>Ej-Sjが含まれていますか?
このように問題は簡単です.私達は後ノードによって大きいから小さい順に並べられます.もし後ノードが等しいなら、前ノードは小さいから大きい順に並べられます.このように順序を並べたら、前ノードより前のノードの数だけ探していけばいいです.
#include 
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int n, bit[maxn];

struct node {
    int s, e, i;

    bool friend operator b.e;
    }
} a[maxn];

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

void updata(int x) {
    while (x <= n) {
        bit[x]++;
        x += lowbit(x);
    }
}

int getsum(int x) {
    int sum = 0;
    while (x) {
        sum += bit[x];
        x -= lowbit(x);
    }
    return sum;
}

int main() {
    while (cin >> n && n) {
        int s[maxn];
        me(bit, 0);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i].s, &a[i].e);
            a[i].i = i;
            a[i].s++;///  s    0，       
        }
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; i++) {
            if (a[i].s == a[i - 1].s && a[i].e == a[i - 1].e)///      ,         
                s[a[i].i] = s[a[i - 1].i];
            else
                s[a[i].i] = getsum(a[i].s);///      
            updata(a[i].s);
        }
        for (int i = 1; i <= n; i++) {
            if (i != n)
                printf("%d ", s[i]);
            else
                printf("%d
", s[i]);
        }
    }
    return 0;
}
 
POJ 1990 MooFest(樹状配列)
2頭の牛i、jが交流する時、交流の最小の音はmax｛v[i]、v[j]*彼らの間の距離です.今はn頭の牛がいます.彼らの間で交流するには少なくとも必要な音量と.
暴力を使うと必ず時間がかかりますので、木の形の配列を使ってもいいです.まず牛を音の値にして、小さい時から大きな順に並べます.そして二つの配列を宣言して、現在入力されている牛の前の位置がそれより小さい牛の個数を記録します.これらの牛の位置と位置を記録します.現在の牛と他の牛の違いをどうやって求めますか?これです.二つの部分に分けて計算します.一つは現在の牛より小さい牛と位置が現在の牛より大きい牛です.位置が小さい牛は計算がいいです.現在の牛の聴力値は現在の牛より小さい牛の位置差を乗じます.大きな牛は計算がちょっと面倒です.現在入力されているすべての牛の位置と、位置が小さい牛の位置と、位置を減らします.それより大きい牛の位置と彼の聴力値を乗じていると、この牛は他の牛と違ってすべての価値があります.聴力順に並べられているので、今の牛の聴力値は一番大きいです.直接乗ればいいです.
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 2e4 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
ll s[maxn], c[maxn];

struct node {
    int v, i;

    bool friend operator
 
POJ 3264 Balanced Lineup(RMQ)
この問題は線分樹で守ることができますが、ここはRMQを使うともっと便利です.
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 5e4 + 10;
const int mod = 1e9 + 7;
const int inf = 1e8;
#define me(a, b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int ma[maxn][40], mi[maxn][40], n, m;

void inct() {
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            ma[i][j] = max(ma[i][j - 1], ma[i + (1 << (j - 1))][j - 1]);
            mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);
        }
}

void print(int l, int r) {
    int k = (int) (log(r - l + 1 + 0.0) / log(2.0));///k = log2(r - l + 1);
    int y = max(ma[l][k], ma[r - (1 << k) + 1][k]);
    int x = min(mi[l][k], mi[r - (1 << k) + 1][k]);
    cout << y - x << endl;
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        me(ma, 0), me(mi, 0);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &ma[i][0]);
            mi[i][0] = ma[i][0];
        }
        inct();
        while (m--) {
            int l, r;
            cin >> l >> r;
            print(l, r);
        }
    }
    return 0;
}
LeetCode 98.Validate Binary Search Tree