algorithm-template

This is a page, which shows some implementations of algorithms that are commonly used in OI.

Greatest Common Divisor is the most basic problem in Math Theorem. In C language .it can be written in briefly two style.

#include <iostream>
using namespace std;



int GCD(int x,int y){
    if(x==0) return y;
    return GCD(y%x,x);
}

// Loop (Recommended);
inline void GCD(int x,int y){
    while(x^=y^=x^=y%=x);return y;
}

The fastest way to judge a prime number

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
using namespace std;

bool vis[10000001];
int prime[10000001];
int n,m;
bool idx[10000000];
void init(){
    memset(vis, true, sizeof(vis));  
    memset(prime,0,sizeof(prime));
    int num = 0;  
    for (int i = 2; i <= n; ++i){  
        if (vis[i] == true){  
            num++;  
            prime[num] = i;  
            idx[i]=true;
        }  
        for (int j = 1; ((j <= num) && (i * prime[j] <= n));  ++j){  
            vis[i * prime[j]] = false;  
            if (i % prime[j] == 0) break;  
        }  
    }  
}

int main(){
    cin>>n>>m;
    init();
    while(m--){
        int s;cin>>s;
        if(idx[s]){
            puts("Yes");
        }else{
            puts("No");
        }
    }
    return 0;
}

This is a dataStructure that can judge two elements whether they are in a same set or not. It is essential in Kruskal Algorithm.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int fa[10001];
int N,M;

int Find(int x){
    int xx=x;
    while(x!=fa[x]) x=fa[x];
    int j;
    while(xx!=x){
        j=fa[xx];
        fa[xx]=x;
        xx=j;
    }
    return x;
}

inline void Union(int x,int y){
    int fx=Find(x);int fy=Find(y);
    if(fx!=fy){
        fa[fx]=fy;
    }
}

inline void init(){
    for(int i=1;i<=N;++i) fa[i]=i;
}

int main(){
    cin>>N>>M;
    init();
    int op,a,b;
    while(M--){
        cin>>op>>a>>b;
        if(op==1){
            Union(a,b);
        }else{
            if(Find(a)==Find(b)){
                puts("Y");
            }else{
                puts("N");
            }
        }
    }
    return 0;
}

A very useful template. It can be used in big integer calculation

Version-1(Negative integer supported | Modulo unsupported | Digit compression supported)

#include <vector>
using std::vector;
#include <sstream>
using std::stringstream;
#include <iterator>
using std::ostream_iterator;
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using std::istream;
using std::ostream;
#include <algorithm>
using std::reverse;
using std::max;
using std::lexicographical_compare;
using std::find;
#include <string>
using std::string;
#include <iterator>
using namespace std;
#include <cmath>

class BigInt : public vector<long long> {
    bool negative;

public:
    BigInt(long long num = 0);
    BigInt operator +(const BigInt&) const ;
    BigInt operator += (const BigInt&);
    BigInt operator -(const BigInt&) const ;
    BigInt operator -= (const BigInt&);
    BigInt operator * (const BigInt&) const ;
    BigInt operator *= (const BigInt&);
    BigInt operator / (long long num) const ;
    BigInt operator ^ (unsigned index) const ;
    inline bool operator < (const BigInt&) const ;
    inline bool operator > (const BigInt&) const ;
    inline bool operator <= (const BigInt&) const ;
    inline bool operator >= (const BigInt&) const ;
    friend inline istream &operator >> (istream&, BigInt&);
    friend inline ostream &operator << (ostream&, BigInt&);
} dp[88][88], ans;

const unsigned sys(100000); // Digit compression

BigInt::BigInt(long long num) {
    negative = num < 0;
    do
        this->push_back(num % sys);
    while (num /= sys);
}

BigInt BigInt:: operator +(const BigInt &num) const {
    BigInt result, a = *this, b = num;
    a.negative = b.negative = false;
    if (this->negative)
        if (num.negative) {
            result = a + b;
            result.negative = true;
            return result;
        }
        else
            return b - a;
    else if (num.negative)
        return a - b;
    else {
        size_t max_size(std::max(num.size(), size()));
        a.resize(max_size, 0);
        b.resize(max_size, 0);
        for (size_t i(0); i < max_size; result[i++] %= sys)
            result.push_back((result[i] += b[i] + a[i]) / sys);
        while (result.size() > 1 && *result.rbegin() == 0)
            result.erase(result.end() - 1);
        return result;
    }
}

BigInt BigInt:: operator += (const BigInt &num) {
    return *this = *this +num;
}

BigInt BigInt:: operator -(const BigInt &num) const {
    BigInt result, a(*this), b(num);
    a.negative = b.negative = false;
    if (negative)
        if (num.negative)
            return b - a;
        else {
            result = a + b;
            result.negative = !result.negative;
            return result;
        }
    else if (num.negative)
        return a + b;
    else {
        if (a < b) {
            a.swap(b);
            a.negative = true;
        }
        b.resize(a.size(), 0);
        for (size_t i(0); i < a.size(); ++i) {
            if (a[i] < b[i])
                a[i] += sys, --a[i + 1];
            a[i] -= b[i];
        }
        while (a.size() > 1 && *a.rbegin() == 0)
            a.erase(a.end() - 1);
        return a;
    }
}

BigInt BigInt:: operator -= (const BigInt &num) {
    return *this = *this -num;
}

BigInt BigInt:: operator *(const BigInt &num) const {
    if (*this == BigInt() || num == BigInt())
        return BigInt();
    BigInt result;
    result.negative = negative ^ num.negative;
    result.resize(size() + num.size(), 0);
    for (size_t i(0); i < size(); ++i)
        for (size_t j(0); j < num.size(); ++j)
            result[i + j] += at(i) * num[j];
    for (size_t i(0); i < result.size() - 1; ++i)
        result[i + 1] += result[i] / sys, result[i] %= sys;
    while (*result.rbegin() == 0)
        result.erase(result.end() - 1);
    return result;
}

BigInt BigInt:: operator *= (const BigInt &num) {
    return *this = *this*num;
}

BigInt BigInt:: operator / (long long num) const {
    BigInt result(*this);
    return result;
}

BigInt BigInt:: operator ^ (unsigned index) const {
    BigInt result(1), base = *this;
    for (; index; base *= base, index >>= 1)
        if (index & 1)
            result *= base;
    return result;
}

Bigint Bigint::operator %(const BigInt& num)const{
    BigInt res=*this/num;
    res=*this-res*num;
    return res;
}

inline bool BigInt:: operator < (const BigInt &num) const {
    if (negative ^ num.negative)
        return negative;
    if (size() == num.size()) {
        for (int i(size() - 1); i >= 0; --i)
            if (at(i) != num[i])
                return at(i) < num[i] ^ negative;
        return false;
    }
    else
        return size() < num.size() ^ negative;
}

inline bool BigInt:: operator > (const BigInt &num) const {
    return num < *this;
}

inline bool BigInt:: operator <= (const BigInt &num) const {
    return !(num < *this);
}

inline bool BigInt:: operator >= (const BigInt &num) const {
    return !(*this < num);
}

inline istream &operator >> (istream &in, BigInt &num) {
    num.clear();
    num.negative = false;
    string data;
    in >> data;
    if (data[0] == '-')
        data.erase(0, 1), num.negative = true;
    int tmp(0);
    for (size_t i(data.size()), cnt(1); i--; cnt *= 10)
        if (cnt < sys)
            tmp += cnt * (data[i] - '0');
        else {
            num.push_back(tmp);
            tmp = data[i] - '0';
            cnt = 1;
        }
    num.push_back(tmp);
    return in;
}

inline ostream &operator << (ostream &out, BigInt &num) {
    if (num.negative)
        out.put('-');
    for (BigInt::reverse_iterator i(num.rbegin()); i < num.rend(); out << *i++)
        if (i != num.rbegin())
            for (int j(0); j < (*i ? int(log10(sys))-int(log10(*i) + 1) :
                log10(sys) - 1); ++j)
                out.put('0');
    return out;
}

Version-2(Negative integer unsupported | Mod supported)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

const int MAXN = 1110;

struct BigInt{
    int len, s[MAXN];
    // Constructor
    BigInt (){
        memset(s,0,sizeof(s));
        len = 1;
    }
    BigInt(int num){*this=num;}
    BigInt(const char *num){*this=num;}

    // Logic Operands
    bool operator < (const BigInt &b){
        if(len != b.len) return len < b.len;
        for(int i = len-1; i >= 0; i--){
            if(s[i] != b.s[i]) return s[i] < b.s[i];
        }
        return false;
    }
    bool operator > (const BigInt &b){
        if(len!=b.len) return len > b.len;
        for(int i=len-1;i>=0;i--){
            if(s[i] != b.s[i]) return s[i]>b.s[i];
        }
        return false;
    }
    bool operator == (const BigInt &b){
        if(len!=b.len) return false;
        for(int i=0;i<len;++i){
            if(s[i]!=b.s[i]) return false;
        }
        return true;
    }
    bool operator != (const BigInt &b){
        return !(*this == b);
    }
    bool operator <= (const BigInt &b){
        return *this<b || *this==b;
    }
    bool operator >= (const BigInt &b){
        return *this>b || *this==b;
    }

    // Arithmetic Operands
    BigInt operator = (const int num){
        char s[MAXN];
        sprintf(s, "%d", num);
        *this=s;
        return *this;
    }
    BigInt operator = (const char *num){
        for(int i = 0; num[i] == '0'; num++) ;
        len = strlen(num);
        for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
        return *this;
    }
    BigInt operator + (const BigInt &b) const{
        BigInt c;
        c.len = 0;
        for(int i = 0, g = 0; g || i < max(len, b.len); i++)
        {
            int x = g;
            if(i < len) x += s[i];
            if(i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    BigInt operator += (const BigInt &b){
        *this = *this + b;
        return *this;
    }
    void clear(){
        while(len > 1 && !s[len-1]) len--;
    }
    BigInt operator * (const BigInt &b){
        BigInt c;
        c.len = len + b.len;
        for(int i = 0; i < len; i++)
        {
            for(int j = 0; j < b.len; j++)
            {
                c.s[i+j] += s[i] * b.s[j];
            }
        }
        for(int i = 0; i < c.len; i++)
        {
            c.s[i+1] += c.s[i]/10;
            c.s[i] %= 10;
        }
        c.clear();
        return c;
    }
    BigInt operator *= (const BigInt &b){
        *this = *this * b;
        return *this;
    }
    BigInt operator - (const BigInt &b){
        BigInt c;
        c.len = 0;
        for(int i=0,g=0;i<len;i++){
            int x=s[i]-g;
            if(i<b.len)x-=b.s[i];
            if(x>=0) g=0;
            else{
                g=1;
                x+=10;
            }
            c.s[c.len++]=x;
        }
        c.clear();
        return c;
    }
    BigInt operator -= (const BigInt &b){
        *this = *this - b;
        return *this;
    }
    BigInt operator / (const BigInt &b){
        BigInt c, f = 0;
        for(int i = len-1; i >= 0; i--)
        {
            f = f*10;
            f.s[0] = s[i];
            while(f >= b)
            {
                f -= b;
                c.s[i]++;
            }
        }
        c.len = len;
        c.clear();
        return c;
    }
    BigInt operator /= (const BigInt &b){
        *this  = *this / b;
        return *this;
    }
    BigInt operator % (const BigInt &b){
        BigInt r = *this / b;
        r = *this - r*b;
        return r;
    }
    BigInt operator %= (const BigInt &b){
        *this = *this % b;
        return *this;
    }
    string str()const{
        string res = "";
        for(int i=0;i<len;i++) res=char(s[i]+'0')+res;
        return res;
    }
};

istream& operator >> (istream &in, BigInt &x){
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream& operator << (ostream &out, const BigInt &x){
    out << x.str();
    return out;
}

int main(){
    BigInt a,b;
    a=100;
    b=2120;
    BigInt c=a+b;
    cout<<c<<" ";
    c=b-a;
    cout<<c<<" ";
    c=a*b;
    cout<<c<<" ";
    c=b/a;
    cout<<c<<" ";
    c=b%a;
    cout<<c<<" ";
}

The simplest linear dataStructure;
It can be used to implement adjacent list in graph structure

/*************************************************************************
    > File Name: LinkList.cpp
    > Author:
    > Mail:
    > Created Time: Fri 07 Oct 2016 11:30:20 PM CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

#define null NULL

struct Node{
    int data;
    Node* Next;
};

Node *head;
Node *tail;
int tot=0;
void Tail_Insert(int v); // Insert to the tail
void Head_Insert(int v); // Insert to the head
void Insert(int idx,int v); // Insert to idx(2<=idx<=tot)
void Remove(idx); // Remove the element on idx
void Pop_Tail();  // Remove the element of the tail
void Pop_Head();  // Remove the element after the head
void Traverse();  // Print the data from head to tail

int main(){
    //head->Next=null;
    //tail=null;
    head=(Node*)malloc(sizeof(Node));
    head->Next=null;
    int N,M;
    cin>>N>>M;
    int op,v;
    while(M--){
        cin>>op;
        switch(op){
            case 1:{
                cin>>v;
                Head_Insert(v);
                break;
            }
            case 2:{
                cin>>v;
                Tail_Insert(v);
                break;
            }
            case 3:{
                int idx;cin>>idx>>v;
                if(idx>=tot){
                    Tail_Insert(v);
                }else{
                    Insert(idx,v);
                }
                break;
            }
            case 4:{
                cin>>v;
                if(v<=tot){
                    Remove(v);
                }else if(tot>0){
                    Pop_Tail();
                }
                break;
            }
            case 5:{
                if(tot>0){
                    Pop_Head();
                }
                break;
            }
            case 6:{
                if(tot>0){
                    Pop_Tail();
                }
                break;
            }
            case 7:{
                Traverse();
                putchar('n');
                break;
            }
        }
    }
}

inline void Tail_Insert(int v){
    ++tot;
    Node* q=(Node*)malloc(sizeof(Node));
    q->data=v;q->Next=null;
    if(tail==null){
        head->Next=q;
        q->Next=null;
        tail=q;
    }else{
        q->Next=tail->Next;
        tail->Next=q;
        tail=q;
    }
}

inline void Head_Insert(int v){
    ++tot;
    Node* q=(Node*)malloc(sizeof(Node));
    q->data=v;q->Next=null;
    if(head->Next==null){
        head->Next=q;
        tail=q;
        q->Next=null;
    }else{
        q->Next=head->Next;
        head->Next=q;
    }
}

inline void Insert(int idx,int data){
    ++tot;
    Node* cur=head->Next;
    for(int i=1;i<idx;++i){
        cur=cur->Next;
    }
    Node* q=(Node*)malloc(sizeof(Node));
    q->data=data;q->Next=cur->Next;
    cur->Next=q;
}

inline void Remove(int idx){
    --tot;
    Node* cur=head->Next;
    for(int i=2;i<idx;++i) cur=cur->Next;
    Node* del=cur->Next;
    cur->Next=del->Next;
    free(del);
}
inline void Pop_Head(){
    --tot;
    Node* del=head->Next;
    head->Next=del->Next;
    free(del);
}
inline void Pop_Tail(){
    --tot;
    Node* cur=head->Next;
    while(cur->Next->Next!=null){
        cur=cur->Next;
    }
    Node* del=cur->Next;
    free(del);
    cur->Next=null;
    tail=cur;
}

inline void Traverse(){
    Node* cur=head->Next;
    while(cur!=null){
        printf("%d ",cur->data);
        cur=cur->Next;
    }
}

Differing from the traditional linklist, the CircleLinkList maintains a tail element whose ‘Next‘ pointer points to the ‘head‘. It can be used to solve Joseph Problem..

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

struct Node{
    int data;
    Node* Next;
};

Node* head;
Node* tail;

inline void Push_back(int v){
    Node *q=(Node*)malloc(sizeof(Node));
    q->data=v;
    if(tail==NULL){
        head->Next=q;
        q->Next=head;
        tail=q;
    }else{
        tail->Next=q;
        q->Next=head;
        tail=q;
    }
}

inline void Push_Front(int v){
    Node* q=(Node*)malloc(sizeof(Node));
    q->data=v;
    if(tail==NULL){
        head->Next=q;
        q->Next=head;
        tail=q;
    }else{
        q->Next=head->Next;
        head->Next=q;
    }
}

inline void Traverse(){
    Node* cur=head->Next;
    while(cur!=head){
        cout<<cur->data<<' ';
        cur=cur->Next;
    }
}

int main(){
    head=(Node*)malloc(sizeof(Node));
    head->Next=head;
    int N;
    cin>>N;
    while(N--){
        int op;cin>>op;
        switch(op){
            case 1:{
                int v;cin>>v;
                Push_Front(v);
                break;
            }
            case 2:{
                int v;cin>>v;
                Push_back(v);
                break;
            }
            case 3:{
                Traverse();
                putchar('n');
                break;
            }
        }
    }
}

Stack is a very essential data structure in OI. It is widely used in various solutions of problems. Its idea is ‘FILO‘ which means First In Last Out. It also can be used to reverse elements in an array.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdio>
using namespace std;

struct Stack{
    int t;
    int bottom;
    int a[10001];
    Stack(){
        memset(a,0,sizeof(a));
        t=bottom=0;
    }
    void push(int x){
        a[++t]=x;
    }
    void pop(){
        if(t==bottom) return;
        else{
            --t;
        }
    }
    int size(){
        return t-bottom;
    }
    int top(){
        return a[t];
    }
};

int main(){
    Stack s;
    for(int i=0;i<10;++i){
        s.push(i);
    }
    while(s.size()){
        cout<<s.top()<<' ';
        s.pop();
    }
    return 0;
}

Queue is also a popular data structure in OI. It is utilized in various things(Like SPFA algorithm). Its idea contrast to that of stack: ‘FIFO‘ ,which means ‘First In First Out‘

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdio>
using namespace std;
#define SIZE 10000
struct Queue{
    int f,t;
    int a[10001];
    int k;

    Queue(){
        f=t=0;
        k=0;
    }
    void push(int x){
        if(t+1>SIZE && f==0){
            return;
        }else if(t+1>SIZE){
            a[t]=x;
            t=0;
        }else{
            a[t++]=x;
        }
        ++k;
    }
    int front(){
        return a[f];
    }
    void pop(){
        if(f!=t){
            f++;
            --k;
            if(f>SIZE) f=0;
        }
    }
    int size(){
       return k;
    }
};

int main(){
    Queue q;
    for(int i=0;i<10;++i) q.push(i);
    while(q.size()){
        cout<<q.front()<<' ';
        q.pop();
    }
    return 0;
}

An optimized version of BST(Binary Search Tree). It utilizes the ‘fix’ value to prevent the tree retrogresses to a linear link. The fix value is a heap and the data value is a BST, thus it is named ‘Treap’.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

struct Node{
    int l,r,w,v,size;
    int fix;
}T[100005];
int _size=0;
int ROOT;

inline void init(){
    srand(19260817); // MOD MOD MOD
}

inline void Update(int k){
    T[k].size=T[T[k].l].size+T[T[k].r].size+T[k].w;
}

inline void left_rot(int &k){
    int t=T[k].r;
    T[k].r=T[t].l;
    T[t].l=k;
    T[t].size=T[k].size;
    Update(k);
    k=t;
}

inline void right_rot(int &k){
    int t=T[k].l;
    T[k].l=T[t].r;
    T[t].r=k;
    T[t].size=T[k].size;
    Update(k);
    k=t;
}

void Insert(int &k,int v){
    if(k==0){
        _size++;
        k=_size;
        T[k].size=T[k].w=1;
        T[k].v=v;
        T[k].fix=rand();
        return;
    }
    T[k].size+=1;
    if(T[k].v==v) T[k].w++;
    else if(T[k].v<v){
        Insert(T[k].r,v);
        if(T[k].fix>T[T[k].r].fix) left_rot(k);
    }else{
        Insert(T[k].l,v);
        if(T[k].fix>T[T[k].l].fix) right_rot(k);
    }
}

void del(int &k,int v){
    if(k==0) return;
    if(T[k].v==v){
        if(T[k].w>1){
            T[k].w--;
            T[k].size--;
            return;
        }
        if(T[k].l*T[k].r==0){
            k=T[k].r+T[k].l;
        }else if(T[T[k].l].fix<T[T[k].r].fix){
            right_rot(k);del(k,v);
        }else{
            left_rot(k);del(k,v);
        }
    }else if(T[k].v>v){
        T[k].size--;
        del(T[k].l,v);
    }else{
        T[k].size--;
        del(T[k].r,v);
    }
}

int Rank(int k,int v){
    if(k==0) return 0;
    if(T[k].v==v) return T[T[k].l].size+1;
    else if(T[k].v<v){
        return T[k].w+T[T[k].l].size+Rank(T[k].r,v);
    }else return Rank(T[k].l,v);
}

int Num(int k,int v){
    if(k==0) return 0;
    if(v<=T[T[k].l].size){
        return Num(T[k].l,v);
    }else if(v>T[T[k].l].size+T[k].w){
        return Num(T[k].r,v-T[T[k].l].size-T[k].w);
    }else return T[k].v;
}
int ans=0;
void query_pre(int k,int v){
    if(k==0) return;
    if(T[k].v<v){
        ans=k;
        query_pre(T[k].r,v);
    }else query_pre(T[k].l,v);
}

void query_son(int k,int v){
    if(k==0) return;
    if(T[k].v>v){
        ans=k;
        query_son(T[k].l,v);
    }else query_son(T[k].r,v);
}

int main(){
    int N;
    cin>>N;
    int op,v;
    while(N--){
        cin>>op>>v;
        switch(op){
            case 1:Insert(ROOT,v);break;
            case 2:del(ROOT,v);break;
            case 3:cout<<Rank(ROOT,v)<<"n";break;
            case 4:cout<<Num(ROOT,v)<<"n";break;
            case 5:{
                ans=0;
                query_pre(ROOT,v);cout<<T[ans].v<<"n";
                break;
            }
            case 6:{
                ans=0;
                query_son(ROOT,v);cout<<T[ans].v<<"n";
                break;
            }
        }
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

int heap[1001000];

#define lson(x) x<<1
#define rson(x) x<<1|1
#define fa(x) x>>1

struct Heap{
    int size;
    Heap(){
        size=0;
    }

    void pushDown(int i){
        int l,r,k;
        while(lson(i)<=size){
            l=lson(i),r=rson(i),k=i;
            if(heap[k]>heap[l]){
                k=l;
            }
            if(r<=size && heap[k]>heap[r]){
                k=r;
            }
            if(k!=i){
                swap(heap[k],heap[i]);
                i=k;
            }else break;
        }
    }

    void pushUp(int i){
        while(fa(i)>=1){
            if(heap[fa(i)]>heap[i]){
                swap(heap[i],heap[fa(i)]);
                i=fa(i);
            }else break;
        }
    }

    void pop(){
        heap[1]=heap[size--];
        pushDown(1);
    }
    int top(){
        return heap[1];
    }
    void insert(int x){
        heap[++size]=x;
        pushUp(size);
    }
};

inline int read(){
    int a=0;
    char ch = getchar();bool flag = false;
    while(ch>'9' || ch<'0' || ch=='-'){
        if(ch=='-') flag=true;
        ch = getchar();
    }
    while(ch>='0' && ch <= '9'){
        a = a*10+ch-'0';
        ch=getchar();
    }
    if(flag) a=-a; 
    return a;
}

int main(){
    Heap h;
    int N;N=read();int k;
    for(int i=1;i<=N;++i){
        k=read();
        h.insert(k);
    }
    while(h.size!=0){
        printf("%d ",h.top());h.pop();
    }
    return 0;
}

Interval Tree is a very useful tree structure, which is widely used to maintain a segment (Like number sequence). It utilizes the thought of divide & conquer.

The graph shows above(Maybe it’s not as beautiful as you thought) describes the appearance of a InvervalTree. As you can see, each nodes maintains a value of an interval, which is built up with a sequence of numbers.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define INF 0x3f3f3f3f
#define MAXN 100100
#define lson(x) x<<1
#define rson(x) x<<1|1
#define Mid(x,y) (x+y)>>1
int A[1001];
inline int read(){ // ReadInt
    char ch;
    bool flag = false;
    int a=0;
    while(!((((ch=getchar())>='0') && (ch<='9')) || (ch=='-')));
    if(ch!='-'){
        a *= 10;
        a += ch - '0';
    }
    else{
        flag = true;
    }
    while(((ch=getchar())>='0')&& (ch<='9')){
        a *= 10;
        a += ch - '0';
    }
    if(flag){
        a = -a;
    }
    return a;
}

struct Node{
    int sum;
    int Max,Min;
    int lson,rson;
    Node(){
        sum=0;
        Max=-INF;
        Min=INF;
        lson=rson=0;
    }
}Tree[1000<<1]; // Double space

inline void Maintain(int k){ // Pass the value of sons to the father node.
    Tree[k].sum=Tree[lson(k)].sum+Tree[rson(k)].sum; // Maintain the sum.
    Tree[k].Max=max(Tree[lson(k)].Max,Tree[rson(k)].Max); // Maintain Max value;
    Tree[k].Min=min(Tree[lson(k)].Min,Tree[rson(k)].Min); // Maintain Min value;
}

void Build(int rt,int l,int r){ // Build up an IntervalTree by using a sequence of number
    Tree[rt].lson=l;Tree[rt].rson=r;
    if(l==r){ // Reach a leaf node
        Tree[rt].sum=A[l];
        Tree[rt].Min=Tree[rt].Max=Tree[rt].sum;
        return;
    }
    int mid=Mid(l,r);
    Build(lson(rt),l,mid); // Build left son(l to mid)
    Build(rson(rt),mid+1,r); // Buld right son(mid+1 to r)
    Maintain(rt); // Maintain the value of father node.
}
/*
* Update a single point of the sequence
*/
void Update(int rt,int p,int value,bool change){
    if(Tree[rt].lson==p && Tree[rt].lson==Tree[rt].rson){
        if(change){ // Change the value
            Tree[rt].sum=value;
            Tree[rt].Max=value;
            Tree[rt].Min=value;
        }else{      // Add value to certain point
            Tree[rt].sum+=value;
            Tree[rt].Max+=value;
            Tree[rt].Min+=value;
        }
        return;
    }
    int mid=Mid(Tree[rt].lson,Tree[rt].rson);
    if(p<=mid){
        Update(lson(rt),p,value,change);
    }else{
        Update(rson(rt),p,value,change);
    }
    Maintain(rt);
}

int QuerySum(int rt,int l,int r){ // Query the sum of inverval [l,r]
    if(Tree[rt].lson==l && Tree[rt].rson==r){
      // Reach the target node
        return Tree[rt].sum;
    }else{
        int mid=Mid(Tree[rt].lson,Tree[rt].rson); // Find the mid point
        if(r<=mid){                                  
          // Cond 1: The interval that we are seeking is contained in the interval of left node
            return QuerySum(lson(rt),l,r);
        }else if(l>mid){                          
          // Cond 2: The interval that we are seeking is contained in the interval in the right node.
            return QuerySum(rson(rt),l,r);
        }else{    
            // IMPORTAINT: the half of the interval that we are seeking is contained 
            // in the interval of left node 
            // and the other half is contained in that of right node.                                  
            return QuerySum(lson(rt),l,mid)+QuerySum(rson(rt),mid+1,r);
        }
    }
}
/*
* The idea is assemble that of QuertSum
*/
int QueryMax(int rt,int l,int r){
    if(Tree[rt].lson==l && Tree[rt].rson==r){
        return Tree[rt].Max;
    }else{
        int mid=Mid(Tree[rt].lson,Tree[rt].rson);
        if(r<=mid){
            return QueryMax(lson(rt),l,r);
        }else if(l>mid){
            return QueryMax(rson(rt),l,r);
        }else return max(QueryMax(lson(rt),l,mid),QueryMax(rson(rt),mid+1,r));
    }
}

int QueryMin(int rt,int l,int r){
    if(Tree[rt].lson==l && Tree[rt].rson==r){
        return Tree[rt].Min;
    }else{
        int mid=Mid(Tree[rt].lson,Tree[rt].rson);
        if(r<=mid){
            return QueryMin(lson(rt),l,r);
        }else if(l>mid){
            return QueryMin(rson(rt),l,r);
        }else return min(QueryMin(lson(rt),l,mid),QueryMin(rson(rt),mid+1,r));
    }
}

#define NL putchar('n')
int main(){
    int N;N=read();
    for(int i=1;i<=N;++i) A[i]=read();
    Build(1,1,N);
    int op;
    while(~scanf("%d",&op)){
        switch(op){
            case 1:{
                int l,r;l=read();r=read();
                cout<<QuerySum(1,l,r);
                NL;
                break;
            }
            case 2:{
                int l,r;l=read();r=read();
                cout<<QueryMax(1,l,r);
                NL;
                break;
            }
            case 3:{
                int l,r;l=read();r=read();
                cout<<QueryMin(1,l,r);
                NL;
                break;
            }
            case 4:{
                int pos,val;pos=read();val=read();
                bool mod=read();
                Update(1,pos,val,mod);
                break;
            }
        }
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

struct Node{
    int Max,Min;
};
Node tree[101000<<1];
int M,N;int Hi;

#define lson(x) x<<1
#define rson(x) x<<1|1

inline void Maintain(){
    for(int i=M-1;i;--i){
        tree[i].Max = max(tree[lson(i)].Max, tree[rson(i)].Max);
        tree[i].Min = min(tree[lson(i)].Min, tree[rson(i)].Min);
    }
}

inline void build(){
    for(M=1;M<=N+1;M<<=1);
    for(int i=M+1;i<=M+N;++i){
        scanf("%d", &tree[i].Max);
        tree[i].Min = tree[i].Max;
    }
    Maintain();
}
int maxn,minm;
inline bool query(int l,int r){
    maxn = -0x3f3f3f3f;
    minm = 0x3f3f3f3f;
    for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1){
        if(~l&1){
            maxn = max(maxn, tree[l^1].Max);
            minm = min(minm, tree[l^1].Min);
        }
        if(r&1){
            maxn = max(maxn, tree[r^1].Max);
            minm = min(minm, tree[r^1].Min);
        }
    }
    return maxn-minm <= Hi;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d", &N, &Hi);
        build();
        int Q;scanf("%d", &Q);
        while(Q--){
            int l,r;scanf("%d%d",&l, &r);
            if(query(l,r)){
                puts("YES");
            }else{
                puts("NO");
            }
        }
    }
    return 0;
}

Dijkstra was created by a computer scientist named Dijkstra. It can be used to calculate shortest paths between one specific vertex and other vertices. This version of Dijkstra is not optimized by Heap thus its total complexity is $O(N^2)$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;

#define MAXN 1001
#define INF 0x3f3f3f3f

struct Edge{
    int v,w;
    Edge(){}
    Edge(int vv,int ww){
        v=vv;w=ww;
    }
};
vector<Edge> g[MAXN];
int dist[MAXN];
bool vis[MAXN];
int N,M;

inline void init(){
    memset(vis,false,sizeof(vis));
    memset(dist,INF,sizeof(dist));
}

inline void AddEdge(int u,int v,int w){
    g[u].push_back(Edge(v,w));
    g[v].push_back(Edge(u,w));
}

inline void Dijkstra(int start){
    vis[start]=true;
    dist[start]=0;
    for(int i=0;i<g[start].size();++i){
        dist[g[start][i].v]=g[start][i].w;
    }
    int MIN;
    int pos=start;
    for(int i=1;i<N;++i){
        MIN=0x3f3f3f3f;
        for(int i=0;i<g[pos].size();++i){
            if(!vis[g[pos][i].v] && MIN>dist[g[pos][i].v]){
                start=g[pos][i].v;
                MIN=dist[start];
            }
        }
        vis[start]=true;
        pos=start;
        for(int i=0;i<g[pos].size();++i){
            if(!vis[g[pos][i].v] && dist[g[pos][i].v]>dist[pos]+g[pos][i].w){
                dist[g[pos][i].v]=dist[pos]+g[pos][i].w;
            }
        }
    }
}

int main(){
    cin>>N>>M;
    int u,v,w;
    init();
    while(M--){
        cin>>u>>v>>w;
        AddEdge(u,v,w);
    }
    cin>>u;
    Dijkstra(u);
    for(int i=1;i<=N;++i){
        printf("%d ",dist[i]);
    }
    return 0;
}