• 神奇的快排… 
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std ;
vector<int>a ;
int n ;
int read() {
    int x = 0 , f = 1 ; char s = getchar () ;
    while(s > '9' || s < '0') {if (s == '-') f = -1 ; s = getchar () ;}
    while(s <='9' && s >='0') {x = x * 10 + (s-'0') ; s = getchar () ;}
    return x * f ; 
}
int main () {
    n = read() ;
    for(int i = 1 ; i <= n ; i ++) {
        int x = read() ;
        a.push_back(x) ;
    }
    sort(a.begin() , a.end() ) ;
    for(int i = 0 ; i < a.size() ; i ++) {
        cout << a[i] << " " ;
    }
    return 0 ;
}
  • 树状数组1 
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 500010
using namespace std ;
int n , m , opt ;
int read() {
    int x = 0 , f = 1 ; char s = getchar () ;
    while(s > '9' || s < '0') {if (s == '-') f = -1 ; s = getchar () ;}
    while(s <='9' && s >='0') {x = x * 10 + (s-'0') ; s = getchar () ;}
    return x * f ;
}
struct Tree {
    int c[maxn] ;
    int lowbit(int x) {
        return x&(-x) ;
    }
    void update(int x ,int k) {
        for(int i = x ; i <= n ; i += lowbit(i) ) {
            c[i] += k ;
        }
    } 
    int query(int x) {
        int ans = 0 ;
        for(int i = x ; i ; i -= lowbit(i)) {
            ans += c[i] ;
        }
        return ans ;
    }
}tree ;
int main () { 
    n = read() , m = read() ;
    for(int i = 1 ; i <= n ; i ++) {
        int x = read() ;
        tree.update(i,x) ;
    }
    for(int i = 1 ; i <= m ; i ++) {
        opt = read() ;
        if(opt == 1) {
            int x , k ;
            x = read() , k = read() ;
            tree.update(x,k) ;
        }else {
            int x , y ;
            x = read() , y = read() ;
            cout << tree.query(y) - tree.query(x-1) <<endl ;
        }
    }
    return 0 ;
}
  • 树状数组2 
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 500010
using namespace std ;
int n , m , opt ;
int read() {
    int x = 0 , f = 1 ; char s = getchar () ;
    while(s > '9' || s < '0') {if (s == '-') f = -1 ; s = getchar () ;}
    while(s <='9' && s >='0') {x = x * 10 + (s-'0') ; s = getchar () ;}
    return x * f ;
}
struct Tree {
    int c[maxn] ;
    int lowbit(int x) {
        return x&(-x) ;
    }
    void update(int x ,int k) {
        for(int i = x ; i <= n ; i += lowbit(i) ) {
            c[i] += k ;
        }
    } 
    int query(int x) {
        int ans = 0 ;
        for(int i = x ; i ; i -= lowbit(i)) {
            ans += c[i] ;
        }
        return ans ;
    }
}tree ;
int a[maxn] ;
int main () { 
    n = read() , m = read() ;
    for(int i = 1 ; i <= n ; i ++) {
        a[i] = read() ;
        int hh = a[i] - a[i-1] ;
        tree.update(i,hh) ;
    }
    for(int i = 1 ; i <= m ; i ++) {
        opt = read() ;
        if(opt == 1) {
            int x , k , y ;
            x = read() , y = read() ,k = read() ;
            tree.update(x,k) ;
            tree.update(y+1,-k) ;
        }else {
            int x , y ;
            x = read() ; //, y = read() ;
            cout << tree.query(x) <<endl ;
        }
    }
    return 0 ;
}

线段树1qwq

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 444444
#define int long long 
using namespace std ;
struct dy{
	int lc , rc , sum , tag ;
}tree[maxn] ;
int n , m , opt ,x , y ,z , a[maxn] ;
void pushup (int u ) {
	tree[u].sum = tree[tree[u].lc].sum + tree[tree[u].rc].sum ;
	return ;
} 
void pushdown(int u , int l , int r) {
	int mid = (l+r) >> 1 ;
	tree[tree[u].lc].sum += tree[u].tag * (mid-l+1) ;
	tree[tree[u].lc].tag += tree[u].tag ;
	tree[tree[u].rc].sum += tree[u].tag * (r-mid) ;
	tree[tree[u].rc].tag += tree[u].tag ;
	tree[u].tag = 0 ;
}
int t = 1 ;
void build (int u , int l ,int r) {
	if(l == r) {
		tree[u].sum = a[l] ;
		return ;
	}
	int mid = (l+r) >> 1 ;
	tree[u].lc = ++t ;
	build(tree[u].lc,l,mid) ;
	tree[u].rc = ++t ;
	build(tree[u].rc,mid+1,r) ;
	pushup(u) ;
}
void update(int u ,int l ,int r,int ll ,int rr ,int w) {
	if(l == ll && r == rr) {
		tree[u].sum += (r-l+1)*w ;
		tree[u].tag += w ;
		return ;
	}
	int mid = (l+r) >> 1 ;
	pushdown(u,l,r) ;
	if(rr <= mid) update(tree[u].lc , l,mid,ll,rr,w) ;
	else if(ll > mid) update(tree[u].rc,mid+1,r,ll,rr,w) ;
	else {
		update(tree[u].lc,l,mid,ll,mid,w) ;
		update(tree[u].rc,mid+1,r,mid+1,rr,w) ;
	}
	pushup(u) ;
}int ans = 0 ;
void query(int u ,int l ,int r,int ll ,int rr) {
	if(l == ll && r == rr) {
		ans += tree[u].sum ;
		return ;
	}
	int mid = (l+r) >> 1 ;
	pushdown(u,l,r) ;
	if(rr <= mid) query(tree[u].lc,l,mid,ll,rr) ;
	else if(ll > mid) query(tree[u].rc,mid+1,r,ll,rr) ;
	else {
		query(tree[u].lc,l,mid,ll,mid) ;
		query(tree[u].rc,mid+1,r,mid+1,rr) ;
	}
	pushup(u) ;
}
int read(){
	int x = 0 , f = 1 ; char s = getchar () ;
	while(s > '9' || s < '0') {if (s == '-') f = -1 ; s = getchar () ;}
	while(s <='9' && s >='0') {x = x * 10 + (s-'0') ; s = getchar () ;}
	return x*f ;
}
signed main () {
	n = read() , m = read() ;
	for(int i = 1 ; i <= n ; i ++) {
		a[i] = read() ;
	}
	build(1,1,n) ;
	for(int i = 1 ; i <= m ; i ++) {
		opt = read() , x = read() , y = read() ;
		if(opt == 1) {
			z = read() ;
			update(1,1,n,x,y,z) ;
		}else {
			ans = 0 ;
			query(1,1,n,x,y) ;
			cout << ans << endl ;
		}
	}
	return 0 ;
}