首页 > 代码库 > [wikioi]线段树练习 2

[wikioi]线段树练习 2

http://codevs.cn/problem/1081/

#include <vector>#include <iostream>#include <string.h>using namespace std;const int MAXN = 100000;struct Line {    int left, right;    int n;};Line tree[MAXN * 3];void buildtr(int left, int right, int k) {    tree[k].left = left;    tree[k].right = right;    tree[k].n = 0;    if (left == right) return;    int mid = (left + right) / 2;    buildtr(left, mid, k * 2);    buildtr(mid + 1, right, k * 2 + 1);}int query(int x, int k) {    if (tree[k].left == x && tree[k].right == x) {        return tree[k].n;    }    int mid = (tree[k].left + tree[k].right) / 2;    if (x <= mid) return query(x, k * 2);    else return query(x, k * 2 + 1);}int query(int l, int r, int k) {    if (tree[k].left == l && tree[k].right == r) {        //cout << "k:" << k << ",l" << l << "r," << r << ",n:" << tree[k].n << endl;        return tree[k].n;    }    int mid = (tree[k].left + tree[k].right) / 2;    if (r <= mid) {        return query(l, r, k * 2);    } else if (l > mid) {        return query(l, r, k * 2 + 1);    } else {        return query(l, mid, k * 2) + query(mid + 1, r, k * 2 + 1);    }}int update(int x, int y, int k) {    int diff = 0;    if (tree[k].left == x && tree[k].right == x) {        diff = y - tree[k].n;        tree[k].n = y;        return diff;    }    int mid = (tree[k].left + tree[k].right) / 2;    if (x <= mid) {        diff = update(x, y, k * 2);    } else {        diff = update(x, y, k * 2 + 1);    }    tree[k].n += diff;    return diff;}int add(int l, int r, int x, int k) {    int diff = 0;    if (tree[k].left == tree[k].right) {        diff = x;        tree[k].n += x;        //cout << "diff:" << x << endl;        return x;    }    int mid = (tree[k].left + tree[k].right) / 2;    if (mid >= r) {        diff = add(l, r, x, k * 2);    } else if (mid < l) {        diff = add(l, r, x, k * 2 + 1);    } else {        diff += add(l, mid, x, k * 2);        diff += add(mid + 1, r, x, k * 2 + 1);    }    tree[k].n += diff;    return diff;}int main() {    int n;    cin >> n;    memset(tree, sizeof(tree), 0);    buildtr(1, n, 1);    for (int i = 1; i <= n; i++) {        int x;        cin >> x;        update(i, x, 1);    }    int m;    cin >> m;    while (m--) {        int c;        cin >> c;        if (c == 1) {            int a, b, x;            cin >> a >> b >> x;            add(a, b, x, 1);        } else if (c == 2) {            int i;            cin >> i;            int res = query(i, i, 1);            cout << res << endl;        }    }}

  

[wikioi]线段树练习 2