세그먼트 트리

• 정당성
  • 세그 : 교환법칙 성립
  • 펜윅 : 교환법칙 성립, 역연산 존재 (ex. +와 -, xor과 xor)
  • 레이지 : 교환법칙 성립, 구간 update할 값을 O(1)에 계산 가능 (ex. +v : +(r-l+1)*v )
  • 스파스 : 교환법칙 성립, 겹쳐도 괜찮음 ( f(a,b,c) == f(f(a,b), f(b,c)) )

struct SegTree {
    ll seg[MAX*4];
    ll (*func)(ll a, ll b), fail;
    ll init(vector<ll> &a, int no, int nl, int nr) {
        if(nl == nr) return seg[no] = a[nl];
        int mid = (nl + nr)/2;
        return seg[no] = func(init(a,no*2,nl,mid), init(a,no*2+1,mid+1,nr));
    }
    ll query(int l, int r, int no, int nl, int nr){
        if(r < nl || nr < l) return fail;
        if(l <= nl && nr <=r) return seg[no];
        int mid = (nl + nr)/2;
        return func(query(l, r, no*2, nl, mid), query(l, r, no*2+1, mid+1, nr));
    }
    ll update(int i, ll v, int no, int nl, int nr) {
        if(i<nl || nr<i) return seg[no];
        if(nl == nr) return seg[no] = v; // += v;
        int mid = (nl + nr)/2;
        return seg[no] = func(update(i,v,no*2,nl,mid), update(i,v,no*2+1,mid+1,nr));
    }
} SEG;


// = main ========================

	SEG.func = [](ll a, ll b) {
		return (ll)(a + b);
	};
    SEG.fail = 0;

 

struct LazySeg {
	ll seg[MAX*4], lazy[MAX*4];
	void prop(int no, int nl, int nr) {
		if (lazy[no] != 0){
			seg[no] += (nr - nl +1)*lazy[no];	// FIX: [l,r] range apply
			if (nl != nr) {
				lazy[no*2] += lazy[no];
				lazy[no*2+1] += lazy[no];
			}
			lazy[no] = 0;
		}
	}
    ll init(vector<ll> &a, int no, int nl, int nr) {
        if (nl == nr) return seg[no] = a[nl];
        int mid = (nl + nr)/2;
        return seg[no] = init(a,no*2,nl,mid) + init(a,no*2+1,mid+1,nr);	// FIX: func
    }
	ll update(int l, int r, ll v, int no, int nl, int nr) {
		prop(no, nl, nr);
		if (r<nl || nr<l) return seg[no];
		if (l <= nl && nr <= r) {
			lazy[no] = v;	// FIX: lazy apply 
			prop(no, nl, nr);
			return seg[no];
		}
		int mid = (nl+nr)/2;
		return seg[no] = update(l,r,v,no*2,nl,mid) + update(l,r,v,no*2+1,mid+1,nr);	// FIX: func
	}
	ll query (int l, int r, int no, int nl, int nr) {
		prop(no, nl, nr);
		if (r<nl || nr<l) return 0;
		if (l <= nl && nr <= r) return seg[no];
		int mid = (nl + nr)/2;
		return query(l,r,no*2,nl,mid) + query(l,r,no*2+1,mid+1,nr);	// FIX: func
	}
} LS;

 

struct GoldSeg {
    static ll safe_add (const ll& a, const ll& b) {
        if (a > -LINF && b > -LINF) return a+b;
        if (a > -LINF) return a;
        if (b > -LINF) return b;
        return -LINF;
    }
    struct Node {
        ll lval = -LINF, rval = -LINF, val = -LINF, all = 0;
        Node operator+ (const Node& n) const { return {safe_add(lval,n.lval), safe_add(rval,n.rval), safe_add(val,n.val), safe_add(all,n.all)}; }
    } seg[MAX*4];
    Node func(Node a, Node b) {
        return {
                max({a.lval, safe_add(a.all,b.lval)}),
                max({safe_add(a.rval,b.all), b.rval}),
                max({a.val, b.val, safe_add(a.rval,b.lval)}),
                max({safe_add(a.all,b.all)})
        };
    }
    Node init(vector<Node> &a, int no, int nl, int nr) {
        if(nl == nr) return seg[no] = a[nl];
        int mid = (nl + nr)/2;
        return seg[no] = func(init(a,no*2,nl,mid), init(a,no*2+1,mid+1,nr));
    }
    Node query(int l, int r, int no, int nl, int nr){
        if(r < nl || nr < l) return Node();
        if(l <= nl && nr <= r) return seg[no];
        int mid = (nl + nr)/2;
        return func(query(l, r, no*2, nl, mid), query(l, r, no*2+1, mid+1, nr));
    }
    Node update(int i, Node v, int no, int nl, int nr) {
        if (i < nl || nr < i) return seg[no];
        if (nl == nr) return seg[no] = seg[no]+v; // = v
        int mid = (nl + nr) / 2;
        return seg[no] = func(update(i, v, no * 2, nl, mid), update(i, v, no * 2 + 1, mid + 1, nr));
    }
} GSEG;

vector<GoldSeg::Node> nodes;

 

struct RectSeg {	// 직사각형들의 넓이를 관리하는 웰논 세그 (boj.kr/3392)
    ll cnt[MAX * 4], rng[MAX * 4], diff[MAX * 4];
    ll init(vector<ll> &zip, int no, int nl, int nr) {    // 압축한 좌표를 토대로, 노드 사이 실제 차이를 계산
        if (nl == nr) return diff[no] = zip[nl] - zip[nl-1];    // 0~1 --> 1
        int mid = (nl + nr)/2;
        return diff[no] = init(zip,no*2,nl,mid) + init(zip,no*2+1,mid+1,nr);
    }
    void prop(int no, int nl, int nr) {
        if (cnt[no] > 0) rng[no] = diff[no]; // colored: return self's width
        else {  // uncolored: just merge childs
            if (nl != nr) rng[no] = rng[no*2] + rng[no*2+1];
            else rng[no] = 0;
        }
    }
    ll query(int l, int r, int no, int nl, int nr) {
        if (r < nl || nr < l) return 0ll;
        if (l <= nl && nr <= r) return rng[no];
        int mid = (nl+nr)/2;
        return query(l, r, no*2, nl, mid) + query(l, r, no*2+1, mid+1, nr);
    }
    void update(int l, int r, int v, int no, int nl, int nr) {
        if (r < nl || nr < l) return;
        if (l <= nl && nr <= r) {
            cnt[no] += v;
            prop(no, nl, nr); return;
        }
        int mid = (nl+nr)/2;
        update(l, r, v, no*2, nl, mid); update(l, r, v, no*2+1, mid+1, nr);
        prop(no, nl, nr);
    }
} RS;

// ========================
RS.init(yzip, 1, 1, N-1);
RS.query(1, N-1, 1, 1, N-1);
RS.update(r.xx+1, r.yy, (r.flag?-1:+1), 1, 1, N-1);

 

struct SparseTable {
    ll arr[MAX][30], lg2[MAX];  // 30=lg2(1e9), 20=lg2(1e6)
    ll (*func)(ll a, ll b);     // f(a,b,c) == f(f(a,b), f(b,c))

    void init(int n) {
        for (int j = 1; (1ull << j) < n; ++j) {
            lg2[(1ull << j)] = j;
            for (int i = 0; i + (1ull << (j-1)) < n; ++i) {
                arr[i][j] = func(arr[i][j-1], arr[i + (1ull << (j-1))][j-1]);
            }
        }
        for (int i = 0; i <= n; ++i) {
            if (!lg2[i]) lg2[i] = lg2[i-1];
        }
    }
    ll query(int l, int r) {
        ll lefts = r - (1ull << lg2[r - l + 1]) + 1;
        return func(arr[l][lg2[r - l + 1]], arr[lefts][lg2[r - l + 1]]);
    }
};