非递归线段树

· · 个人记录

真好写，常数也小，mark 一下，万一用得上。

先把区间移到 [n, 2n)，每次建树相当于以 2 为块长分块，左右散块暴力处理，再递归建树。

父亲儿子关系还是 x\to 2x, 2x + 1，非常优秀。

写成左闭右开会比较方便。丢个 树状数组 1 的代码：

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll N = 5e5 + 9;
ll n, m, tr[N << 1];
void upd(ll x, ll k) {
    for(x += n - 1; x; x >>= 1) tr[x] += k;
}
ll query(ll l, ll r) {
    ll res = 0;
    for(l += n - 1, r += n - 1; l < r; l >>= 1, r >>= 1) {
        if(l & 1) res += tr[l], ++l;
        if(r & 1) --r, res += tr[r];
    }
    return res;
}
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    n = read(), m = read();
    rep(i, 1, n) tr[i + n - 1] = read();
    per(i, (n << 1) - 1, 2) tr[i >> 1] += tr[i];
    while(m--) {
        ll op = read(), x = read(), y = read();
        if(op == 1) upd(x, y);
        else write(query(x, y + 1)), putchar('\n');
    }
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}

我们发现这东西方便支持 \mathcal O(len + \log n) 的区间修改。丢一个超小常数的 NOI2017 整数 2log 代码：

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 3e7 + 998;
int n, len;
int a[N], tr[N << 1];
int query(int r) {
    if(!r) return -1;
    int l = 0, res = -1;
    for(l += len, r += len; l < r; l >>= 1, r >>= 1) {
        if(l & 1) res = max(res, tr[l]), ++l;
        if(r & 1) --r, res = max(res, tr[r]);
    }
    return res;
}
void upd(int l, int r) {
    ++r;
    rep(i, l, r) tr[i + len] = (a[i] ? i : -1);
    for(l = (l + len) >> 1, r = (r + len) >> 1; l; l >>= 1, r >>= 1) {
        rep(i, l, r) tr[i] = max(tr[i << 1], tr[i << 1 | 1]);
    }
}
void add(int x, int k) {
    a[x] += k;
    int l = x, r = x;
    while(a[r] == 2 || a[r] == -2) a[r + 1] += a[r] / 2, a[r] = 0, ++r;
    upd(l, r);
}
bool ask(int x) {
    int y = query(x);
    if(!~y) {
        if(!a[x]) return 0;
        return 1;
    }
    if(!a[x]) return a[y] == -1;
    return a[y] != -1;
}
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    n = read(), (*new int) = read(), (*new int) = read(), (*new int) = read();
    len = n * 30 + 64;
    rep(i, 0, (len << 1)) tr[i] = -1;
    while(n--) {
        int op = read(), x = read();
        if(op == 1) {
            int y = read(), sgn = 1;
            if(x < 0) x = -x, sgn = -1;
            rep(i, 0, 30) {
                if((x >> i) & 1) add(y + i, sgn);
            }
        }
        else write(ask(x)), putchar('\n');
    }
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}

区间修改如果不用标记永久化有点麻烦，不过也能做。丢个线段树 2 代码：

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll N = 5e5 + 9, Mod = 571373;
ll n, m, d, tr[N << 1], add[N << 1], mul[N << 1];
bool tagged[N << 1];
void pushtag(ll x, ll tadd, ll tmul, ll len) {
    tr[x] = (tr[x] * tmul + tadd * len) % Mod;
    if(x < n) {
        tagged[x] = 1;
        mul[x] = mul[x] * tmul % Mod;
        add[x] = (add[x] * tmul + tadd) % Mod;
    }
}
void pushdown(ll p) {
    p += n - 1;
    ll len = 1 << (d - 1);
    per(dep, d, 1) {
        ll u = p >> dep;
        if(tagged[u]) {
            pushtag(u << 1, add[u], mul[u], len);
            pushtag(u << 1 | 1, add[u], mul[u], len);
            tagged[u] = 0, add[u] = 0, mul[u] = 1;
        }
        len >>= 1;
    }
}
void pushup(ll p) {
    for(p = (p + n - 1) >> 1; p; p >>= 1) {
        if(!tagged[p]) tr[p] = (tr[p << 1] + tr[p << 1 | 1]) % Mod;
    }
}
void upd(ll l, ll r, ll tadd, ll tmul) {
    ++r;
    ll pl = l, pr = r, len = 1;
    pushdown(l), pushdown(r - 1);
    for(l += n - 1, r += n - 1; l < r; l >>= 1, r >>= 1, len <<= 1) {
        if(l & 1) pushtag(l, tadd, tmul, len), ++l;
        if(r & 1) --r, pushtag(r, tadd, tmul, len);
    }
    pushup(pl), pushup(pr - 1);
}
ll query(ll l, ll r) {
    ++r;
    pushdown(l), pushdown(r - 1);
    ll res = 0;
    for(l += n - 1, r += n - 1; l < r; l >>= 1, r >>= 1) {
        if(l & 1) res += tr[l], ++l;
        if(r & 1) --r, res += tr[r];
    }
    return res % Mod;
}
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    n = read(), m = read(), (*new ll) = read();
    rep(i, 1, n) tr[i + n - 1] = read();
    per(i, (n << 1) - 1, 2) (tr[i >> 1] += tr[i]) %= Mod;
    while((1 << (d + 1)) <= n) ++d;
    ++d;
    fill(mul + 1, mul + n + 1, 1ll);
    while(m--) {
        ll op = read(), x = read(), y = read();
        if(op == 1) {
            ll z = read();
            upd(x, y, 0, z);
        }
        else if(op == 2) {
            ll z = read();
            upd(x, y, z, 1);
        }
        else write(query(x, y)), putchar('\n');
    }
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}