实用数据结构(三)

这篇博文介绍一下线段树以及应用

线段树概论

线段树求区间和

CH4301

const int maxn = 500000 + 2;
const int inf = maxn;
int n, m;
int A[maxn];

class SegTree {
public:
    int l, r, dat;
    int sum, lmax, rmax;
};

typedef SegTree Node;

SegTree t[maxn * 4];

void build(int p, int l, int r) {
    t[p].l = l;
    t[p].r = r;

    if(l == r) {
        t[p].dat = t[p].sum = t[p].lmax = t[p].rmax = A[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);

    t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
    t[p].lmax = max(t[p << 1].lmax, t[p << 1].sum + t[p << 1 | 1].lmax);
    t[p].rmax = max(t[p << 1 | 1].rmax, t[p << 1 | 1].sum + t[p << 1].rmax);
    t[p].dat = max(max(t[p << 1].dat, t[p << 1 | 1].dat), t[p << 1].rmax + t[p << 1 | 1].lmax);
}

void change(int p, int x, int v) {
    if(t[p].l == t[p].r) {
        t[p].sum = t[p].dat = t[p].lmax = t[p].rmax = v;
        return;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if(x <= mid) change(p << 1, x, v);
    else change(p << 1 | 1, x, v);

    t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
    t[p].lmax = max(t[p << 1].lmax, t[p << 1].sum + t[p << 1 | 1].lmax);
    t[p].rmax = max(t[p << 1 | 1].rmax, t[p << 1 | 1].sum + t[p << 1].rmax);
    t[p].dat = max(max(t[p << 1].dat, t[p << 1 | 1].dat), t[p << 1].rmax + t[p << 1 | 1].lmax);
}

Node ask(int p, int x, int y) {
    // ask [x, y] dat
    if(x <= t[p].l && t[p].r <= y) return t[p];

    Node nl, nr, ans;
    nl.lmax = nl.rmax = nl.sum = nl.dat = nr.lmax = nr.rmax = nr.dat = nr.sum = -inf;
    ans.sum = 0;

    int mid = (t[p].l + t[p].r) >> 1;
    if(x <= mid) {
        nl = ask(p << 1, x, y);
        ans.sum += nl.sum;
    }
    if(y > mid) {
        nr = ask(p << 1 | 1, x, y);
        ans.sum += nr.sum;
    }

    ans.dat = max(max(nl.dat, nr.dat), nl.rmax + nr.lmax);
    ans.lmax = max(nl.lmax, nl.sum + nr.lmax);
    ans.rmax = max(nr.rmax, nr.sum + nl.rmax);

    if(x > mid) ans.lmax = max(ans.lmax, nr.lmax);
    if(y <= mid) ans.rmax = max(ans.rmax, nl.rmax);

    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    _rep(i, 1, n) scanf("%d", &A[i]);
    build(1, 1, n);

    while (m--) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);

        if(op == 1) {
            if(x > y) swap(x, y);
            cout << ask(1, x, y).dat << endl;
        }
        if(op == 2) change(1, x, y);
    }
}

线段树求区间和(有条件)

如果线段树求区间和加了一些条件
比如在区间和相同的时候, 要求 $[l, r], l$ 尽量小, 如果还有多解, 要求 $r$ 也尽量小
此类问题可以对线段树维护的信息进行调整

输入的时候就对sum[]前缀和预处理
lmax换成lx, 表示从左边开始, 能够扩展的最长前缀的下标
rmax换成rx, 表示从右边开始, 能够扩展的最长后缀的下标
dat表示当前这个[l, r]区间, 能够找到的最优连续子区间是pair<int, int> dat

LA3938

#define lowbit(i) (i & (-i))

typedef pair<int, int> PII;
const int maxn = 500000 + 2;
llong sum[maxn];
int n, m;

void init() {
    Set(sum, 0);
}

llong cal(const PII x) {
    return sum[x.second] - sum[x.first - 1];
}

PII better(const PII& lhs, const PII& rhs) {
    llong suml = cal(lhs), sumr = cal(rhs);
    if(suml != sumr) return suml > sumr ? lhs : rhs;
    return lhs < rhs ? lhs : rhs;
}


class SegTree {
public:
    int l, r;

    PII dat;
    int lx, rx;
};

SegTree t[maxn * 4];
typedef SegTree Node;

Node combine(const Node& lhs, const Node& rhs) {
    Node ret;
    ret.l = lhs.l; ret.r = rhs.r;

    ret.lx = better(PII(lhs.l, lhs.lx), PII(lhs.l, rhs.lx)).second;
    ret.rx = better(PII(rhs.rx, rhs.r), PII(lhs.rx, rhs.r)).first;
    // then ret.dat = cross
    ret.dat = better(better(lhs.dat, rhs.dat), PII(lhs.rx, rhs.lx));

    return ret;
}

void build(int p, int l, int r) {
    t[p].l = l;
    t[p].r = r;

    if(l == r) {
        t[p].lx = t[p].rx = l;
        t[p].dat = PII(l, l);
        return;
    }

    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);

    t[p].lx = better(PII(t[p << 1].l, t[p << 1].lx), PII(t[p << 1].l, t[p << 1 | 1].lx)).second;
    t[p].rx = better(PII(t[p << 1 | 1].rx, t[p << 1 | 1].r), PII(t[p << 1].rx, t[p << 1 | 1].r)).first;
    t[p].dat = better(better(t[p << 1].dat, t[p << 1 | 1].dat), PII(t[p << 1].rx, t[p << 1 | 1].lx));
}

Node ask(int p, int x, int y) {
    if(x <= t[p].l && t[p].r <= y) return t[p];

    int mid = (t[p].l + t[p].r) >> 1;
    Node ans;

    if(x <= mid && mid < y) {
        // both left tree and right tree
        ans = combine(ask(p << 1, x, y), ask(p << 1 | 1, x, y));
    }
    else if(x <= mid) {
        // only left
        ans = ask(p << 1, x, y);
    }
    else if(mid < y) {
        ans = ask(p << 1 | 1, x, y);
    }

    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 1;
    while (scanf("%d%d", &n, &m) != EOF) {
        init();
        _rep(i, 1, n) {
            llong x;
            scanf("%lld", &x);
            sum[i] = sum[i - 1] + x;
        }

        build(1, 1, n);
        printf("Case %d:\n", kase++);

        _rep(i, 1, m) {
            int x, y;
            scanf("%d%d", &x, &y);
            PII res = ask(1, x, y).dat;
            printf("%d %d\n", res.first, res.second);
        }
    }
}

线段树+树状数组处理区间增加问题

CH4302

const int maxn = 500000 + 10;
int n, m;

llong A[maxn], B[maxn];
llong fwick[maxn];

llong gcd(llong a, llong b) {
    return b ? gcd(b, a % b) : a;
}

void add(int x, llong d) {
    for(; x <= n; x += lowbit(x)) fwick[x] += d;
}

llong sum(int x) {
    llong ret = 0;
    for(; x > 0; x -= lowbit(x)) ret += fwick[x];
    return ret;
}

void init() {
    Set(A, 0);
    Set(B, 0);
    Set(fwick, 0);
}

class SegTree {
public:
    int l, r;
    llong dat;
};

SegTree t[maxn * 4];
typedef SegTree Node;

void build(int p, int l, int r) {
    t[p].l = l; t[p].r = r;
    if(l == r) {
        t[p].dat = B[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);

    t[p].dat = gcd(t[p << 1].dat, t[p << 1 | 1].dat);
}

void change(int p, int x, llong v) {
    if(t[p].l == t[p].r) {
        t[p].dat += v;
        return;
    }

    int mid = (t[p].l + t[p].r) >> 1;
    if(x <= mid) change(p << 1, x, v);
    else change(p << 1 | 1, x, v);

    t[p].dat = gcd(t[p << 1].dat, t[p << 1 | 1].dat);
}

llong ask(int p, int l, int r) {
    if(l <= t[p].l && t[p].r <= r) {
        return abs(t[p].dat);
    }

    int mid = (t[p].l + t[p].r) >> 1;

    llong ret = 0;

    if(l <= mid) ret = gcd(ret, ask(p << 1, l, r));
    if(r > mid) ret = gcd(ret, ask(p << 1 | 1, l, r));

    return abs(ret);
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    scanf("%d%d", &n, &m);

    _rep(i, 1, n) {
        scanf("%lld", &A[i]);
        B[i] = A[i] - A[i - 1];
    }

    // then build segTree
    build(1, 1, n);

    _for(i, 0, m) {
        // query
        char str[2];
        scanf("%s", str);
        int l, r;
        scanf("%d%d", &l, &r);

        if(str[0] == 'Q') {
            //
            llong al = A[l] + sum(l);
            llong val = l < r ? ask(1, l + 1, r) : 0;
            printf("%lld\n", gcd(al, val));
        }

        if(str[0] == 'C') {
            //
            llong d;
            scanf("%lld", &d);
            change(1, l, d);
            if(r < n) change(1, r + 1, -d);

            add(l, d);
            add(r + 1, -d);
        }
    }
}