Segment Tree + lazy tag (線段樹+懶標記)

區間改值用segment tree+lazy tag實作時，複雜度還是只有O(lg N)
指標版的線段樹

模板題：IOICamp Judge 23

//Segment Tree (pointer), take sum as example
// lazy tag

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <assert.h>   // modify 's   assert
using namespace std;

struct Node {
    long long int val, tag;
    Node *lc, *rc;
    Node(){
        tag=0;
        val=0;
        lc = NULL;
        rc = NULL;
    }
    void pull () {
        val = lc->val + rc->val;
    }
};

const int MAX_N = 100003;

int n, v[MAX_N+1];

void input(int m) {
    memset(v,0,sizeof(v));
    for (int x=1;m>=x;x++) scanf("%d",&v[x]);
}

Node* build(int L, int R) {
    Node *node = new Node();
    if (L==R) {
        node->val = v[L];
        return node;
    }
    int mid = (L+R) >> 1;
    node->lc = build(L,mid);
    node->rc = build(mid+1,R);
    node->pull();
    return node;
}

void push(Node* node, int L,int R) {
    if (!node->tag) return;
    if (L!=R) {   //check leaf
        int mid= (L+R) >> 1;
        node->lc->tag += node->tag;
        node->rc->tag += node->tag;
        node->lc->val += node->tag * (mid - L +1);   //因為tag��表示"之後"的要~~~，所以目前的要處理一下 
        node->rc->val += node->tag * (R - mid);
    }
    node->tag = 0;
}

void modify( Node* node, int L, int R, int ql, int qr,long long int d) {    // 區間修改  |  d : value
    if (ql > R || qr < L) return;
    if (ql<=L && R<=qr) {
        node->tag += d;
        node->val += d*(R-L+1);
        return;
    }
    
    push(node,L,R);
    int mid = (L+R) >> 1;
    modify(node->lc, L,mid,ql,qr,d);
    modify(node->rc,mid+1,R,ql,qr,d);
    node->pull();
}

long long int query(Node* node, int L,int R, int ql, int qr) {
    if (ql > R || qr< L)  return 0;   //mission impossible
    if (ql<=L && R<= qr) return node->val;
    push(node,L,R);
    int mid = (L+R) >> 1;
    return query(node->lc,L,mid,ql,qr) + query(node->rc, mid+1, R ,ql,qr);
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int q;
        scanf("%d %d",&n,&q);
        input(n);
        Node* root = build(1,n);
        for (int i=0;q>i;i++) {
            string k;
            cin >> k;
            if (k=="add") {   //改區間值(加法) 
                int ql,qr,val;
                scanf("%d %d %d",&ql,&qr,&val);
                modify(root,1,n,ql,qr,val);
            }
            else if (k=="query") {
                int l,r;
                scanf("%d %d",&l,&r);
                printf("%lld\n",query(root,1,n,l,r));
            }
        }
    }
    
}

Minimum Spanning Tree(最小生成樹) 模板

Minimum Spanning Tree 模板

我是使用Kruskal演算法。Prim演算法在這裡。這裡是另外一個Kruskal演算法。

理論是說：如果兩個MST之間有一條路徑e，使得花費為最小，那這條路徑必定是大MST的其中一條。複雜度是 O(E lg E)

實作細節：
(1)每一個小MST利用Disjoint Set來實作，Find跟Union加上一些小技巧，即可變成                        O( alpha(N) )。

(2)邊要記得先排序，必要的時候記得定義<運算子

模板題：
(1) IOICamp Judge 40
(2) http://poj.org/problem?id=1258
(3) http://zerojudge.tw/ShowProblem?problemid=a129
(4) UVA 11631 - Dark roads  https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2678

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N=10002;
const int MAX_M=100002;

struct edg {
    int a,b,c;
} e[MAX_M];

struct DisjointSet {
    int p[MAX_N+1];
    int rank[MAX_N+1];
    void init(int n) {
        for (int i=1;n>=i;i++) {
            p[i]=i;
            rank[i]=1;
        }
    }
    int Find(int x) {
        return x==p[x]?x:(p[x]=Find(p[x]));
    }
    void Union(int x,int y) {
        if (rank[x]<rank[y]) {
            p[Find(x)] = Find(y);
        }
        else {
            p[Find(y)] = Find(x);
        }
    }
} djs;

bool operator <(const edg& e1, const edg& e2) {
    return e1.c < e2.c;
}

long long int Kruskal (int n,int m) { // name of the algorithm
    long long min_cost=0;
    djs.init(n);
    sort(e,e+m);
    int i,j; //i-->計次, j-->第幾條邊
    for (int i=0,j=0; i<n-1 && j<m; i++) {
        while (djs.Find(e[j].a) == djs.Find(e[j].b)) j++;  //判斷��否已經在同一個MST
        djs.Union(e[j].a,e[j].b);
        min_cost+=e[j].c;
        j++; 
    }
    return min_cost;
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=0;m>x;x++) {
            int i,j,k;
            scanf("%d %d %d",&i,&j,&k);
            e[x].a=i;
            e[x].b=j;
            e[x].c=k;
        }
        long long ans = Kruskal(n,m);
        printf("%lld\n",ans);
    }
}