线段树：
一、单点修改，区间查询

创新互联公司是一家专注于网站制作、成都网站建设与策划设计,大通网站建设哪家好?创新互联公司做网站,专注于网站建设十载,网设计领域的专业建站公司;建站业务涵盖:大通等地区。大通做网站价格咨询:028-86922220

#pragma GCC optimize(3,"Ofast","inline")
#includeusing namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;
int n, Q;
int a[maxn];
int suma[maxn];
typedef struct
{int l, r;
	int sum;
}T;
T t[maxn<< 1];

inline void build(int rt, int l, int r)
{t[rt].l = l;
	t[rt].r = r;
	if (l == r)
	{t[rt].sum = a[l];
		return;
	}
	int mid = (l + r) >>1;
	build(rt<< 1, l, mid);
	build(rt<< 1 | 1, mid + 1, r);
	t[rt].sum = t[rt<< 1].sum + t[rt<< 1 | 1].sum;
}
inline int interval_add(int rt, int l, int r)
{if (t[rt].l >= l && t[rt].r<= r)return t[rt].sum;
	if (t[rt].l >r || t[rt].r< l)return 0;
	int temp = 0;
	if (t[rt<< 1].r >= l)temp += interval_add(rt<< 1, l, r);
	if (t[rt<< 1 | 1].l<= r)temp += interval_add(rt<< 1 | 1, l, r);
	return temp;
}
inline void point_modify(int rt, int pos, int val)
{if (t[rt].l == t[rt].r)
	{t[rt].sum += val;
		return;
	}
	if (pos<= t[rt<< 1].r)point_modify(rt<< 1, pos, val);
	else point_modify(rt<< 1 | 1, pos, val);
	t[rt].sum = t[rt<< 1].sum + t[rt<< 1 | 1].sum;
	return;
}
int main()
{ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >>n;
	for (int i = 1; i<= n; i++)cin >>a[i], suma[i] = suma[i - 1] + a[i];
	build(1, 1, n);
	cin >>Q;
	while (Q--)
	{bool f;
		cin >>f;
		if (f)
		{	int l, r;
			cin >>l >>r;
			cout<< interval_add(1, l, r)<< "\n";
		}
		else
		{	int p, v;
			cin >>p >>v;
			point_modify(1, p, v);
			a[p] += v;
			for (int i = 1; i<= n; i++)cout<< a[i]<< " ";
			cout<< "\n";
		}
	}
}

二.区间修改，单点查询

#pragma GCC optimize(3,"Ofast","inline")
#includeusing namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;
int n, Q;
int a[maxn];
int suma[maxn];
typedef struct
{int l, r;
	int sum;
}T;
T t[maxn<< 1];

inline void build(int rt, int l, int r)
{t[rt].l = l;
	t[rt].r = r;
	if (l == r)
	{t[rt].sum = a[l];
		return;
	}
	int mid = (l + r) >>1;
	build(rt<< 1, l, mid);
	build(rt<< 1 | 1, mid + 1, r);
}
inline void interval_modify(int rt, int l, int r, int val)
{if (t[rt].l >= l && t[rt].r<= r)
	{t[rt].sum += val;
		return;
	}
	int mid = t[rt].l + t[rt].r >>1;
	if (l<= mid)interval_modify(rt<< 1, l, r, val);
	if (r >mid)interval_modify(rt<< 1 | 1, l, r, val);
}
inline int point_ask(int rt, int pos)
{int ans = 0;
	ans += t[rt].sum;
	if (t[rt].l == t[rt].r)return ans;
	int mid = t[rt].l + t[rt].r >>1;
	if (pos<= mid) ans += point_ask(rt<< 1, pos);
	if (pos >mid)ans += point_ask(rt<< 1 | 1, pos);
	return ans;
}
int main()
{ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >>n; cin >>Q;
	for (int i = 1; i<= n; i++)cin >>a[i], suma[i] = suma[i - 1] + a[i];
	build(1, 1, n);

	while (Q--)
	{bool f;
		cin >>f;
		if (f)
		{	int l, r, v;
			cin >>l >>r >>v;
			interval_modify(1, l, r, v);
			for (int i = l; i<= r; i++)a[i] += v;
			for (int i = 1; i<= n; i++)cout<< a[i]<< " ";
			cout<< "\n";
		}
		else
		{	int pos;
			cin >>pos;
			cout<< point_ask(1, pos)<< "\n";
		}
	}
	return 0;
}

扫描线法

#pragma GCC optimize(3,"Ofast","inline")
#includeusing namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
typedef struct line
{double x, y1, y2;
	int c;
	bool friend operator<(line p, line q)
	{return p.x< q.x;
	}
}A;
A a[maxn<< 1];
typedef struct tree
{int l, r;
	int cnt;
	double len;
}T;
T t[maxn<< 2];
int n;
double raw[maxn<< 1];
int cnt;
double ans;
int val[maxn<< 1][2];

inline void build(int rt, int l, int r)
{t[rt].l = l;
	t[rt].r = r;
	t[rt].cnt = 0;
	t[rt].len = 0;
	if (l == r)return;
	int mid = l + r >>1;
	build(rt<< 1, l, mid);
	build(rt<< 1 | 1, mid + 1, r);
}
void push_up(int rt)
{if (t[rt].cnt >0)t[rt].len = raw[t[rt].r + 1] - raw[t[rt].l];
	else if (t[rt].l == t[rt].r)t[rt].len = 0;
	else t[rt].len = t[rt<< 1].len + t[rt<< 1 | 1].len;
}
void interval_modify(int rt, int l, int r, int val)
{if (t[rt].l >= l && t[rt].r<= r)
	{t[rt].cnt += val;
		push_up(rt);
		return;
	}
	int mid = t[rt].l + t[rt].r >>1;
	if (l<= mid)interval_modify(rt<< 1, l, r, val);
	if (r >mid)interval_modify(rt<< 1 | 1, l, r, val);
	push_up(rt);
}
int main()
{ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int casenum = 0;
	while (cin >>n && n)
	{cnt = 0;
		ans = 0;
		for (int i = 1; i<= n; i++)
		{	double x1, y1, x2, y2;
			cin >>x1 >>y1 >>x2 >>y2;
			a[i * 2 - 1] = {x1,y1,y2,1 };
			a[i * 2] = {x2,y1,y2,-1 };
			raw[++cnt] = y1;
			raw[++cnt] = y2;
		}
		sort(a + 1, a + 1 + 2 * n);
		sort(raw + 1, raw + 1 + cnt);
		cnt = unique(raw + 1, raw + 1 + cnt) - (raw + 1);
		for (int i = 1; i<= n * 2; i++)
		{	val[i][0] = lower_bound(raw + 1, raw + 1 + cnt, a[i].y1) - raw;
			val[i][1] = lower_bound(raw + 1, raw + 1 + cnt, a[i].y2) - raw;
		}
		build(1, 1, cnt);
		for (int i = 1; i<= 2 * n; i++)
		{	interval_modify(1, val[i][0], val[i][1] - 1, a[i].c);
			ans += (a[i + 1].x - a[i].x) * t[1].len;
		}
		cout<< "Test case #"<< ++casenum<< "\n";
		cout<< "Total explored area: "<< fixed<< setprecision(2)<< ans<< "\n";
		cout<< "\n";
	}
	return 0;
}

单点修改，区间查询大子段和

#pragma GCC optimize(3,"Ofast","inline")
#includeusing namespace std;
typedef long long ll;
const int maxn = 5e5 + 100;
int n, Q;
int a[maxn];
int suma[maxn];
typedef struct node
{int l, r;
	int sum;
	int dat;
	int lmax, rmax;
	node()
	{l = r = sum = dat = lmax = rmax = 0;
	}
}T;
T t[maxn<< 2];

inline void build(int rt, int l, int r)
{t[rt].l = l;
	t[rt].r = r;
	if (l == r)
	{t[rt].sum = a[l];
		t[rt].lmax = t[rt].rmax = t[rt].dat = a[l];
		return;
	}
	int mid = (l + r) >>1;
	build(rt<< 1, l, mid);
	build(rt<< 1 | 1, mid + 1, r);
	t[rt].sum = t[rt<< 1].sum + t[rt<< 1 | 1].sum;
	t[rt].lmax = max(t[rt<< 1].lmax, t[rt<< 1].sum + t[rt<< 1 | 1].lmax);
	t[rt].rmax = max(t[rt<< 1 | 1].rmax, t[rt<< 1].rmax + t[rt<< 1 | 1].sum);
	t[rt].dat = max(t[rt<< 1].dat, t[rt<< 1 | 1].dat);
	t[rt].dat = max(t[rt].dat, t[rt<< 1].rmax + t[rt<< 1 | 1].lmax);
}

inline void point_modify(int rt, int pos, int val)
{if (t[rt].l == t[rt].r)
	{t[rt].sum = t[rt].dat = t[rt].lmax = t[rt].rmax = val;
		return;
	}
	int mid = t[rt].l + t[rt].r >>1;

	if (pos<= mid)point_modify(rt<< 1, pos, val);
	else point_modify(rt<< 1 | 1, pos, val);
	t[rt].sum = t[rt<< 1].sum + t[rt<< 1 | 1].sum;
	t[rt].lmax = max(t[rt<< 1].lmax, t[rt<< 1].sum + t[rt<< 1 | 1].lmax);
	t[rt].rmax = max(t[rt<< 1 | 1].rmax, t[rt<< 1].rmax + t[rt<< 1 | 1].sum);
	t[rt].dat = max(t[rt<< 1].dat, t[rt<< 1 | 1].dat);
	t[rt].dat = max(t[rt].dat, t[rt<< 1].rmax + t[rt<< 1 | 1].lmax);
	return;
}

T interval_ask(int rt, int l, int r)                       
{	//此时的ask函数返回的是临时开的T，想一想为什么，如果是void类型ask，每次ask一个区间（l,r）dat，lmax,rmax都会随着l,r不同而修改，一定会影响后续ask
	if (t[rt].l >= l && t[rt].r<= r)return t[rt];
	int mid = t[rt].l + t[rt].r >>1;

	if (l<= mid && r >mid)
	{T tt, tl, tr;
		tl = interval_ask(rt<< 1, l, r);
		tr = interval_ask(rt<< 1 | 1, l, r);
		tt.sum = tl.sum + tr.sum;
		tt.lmax = max(tl.lmax, tl.sum + tr.lmax);
		tt.rmax = max(tr.rmax, tl.rmax + tr.sum);
		tt.dat = max(tl.dat, tr.dat);
		tt.dat = max(tt.dat, tl.rmax + tr.lmax);
		return tt;
	}
	else if (l<= mid)
	{return interval_ask(rt<< 1, l, r);
	}
	else if (r >mid)
	{return interval_ask(rt<< 1 | 1, l, r);
	}
}
int main()
{ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >>n >>Q;
	for (int i = 1; i<= n; i++)cin >>a[i];
	build(1, 1, n);
	while (Q--)
	{int k, x, y;
		cin >>k >>x >>y;
		if (k & 1)
		{	if (x >y)swap(x, y);
			T ans = interval_ask(1, x, y);
			cout<< ans.dat<< "\n";
		}
		else
		{	point_modify(1, x, y);
		}
	}
	return 0;
}

图论补充：第K短路（A*）

//Made In Heaven
#pragma GCC optimize(3, "Ofast", "inline")
#includeusing namespace std;
typedef long long ll;
const int maxn = 1e4 + 1000;
int n, m;
int S, E, K, T;
int dis[maxn];
int h1[maxn], h2[maxn];
bool vis1[maxn];
int num1, num2;
typedef struct
{int nt, to, w;
}EDGE;
EDGE e1[maxn], e2[maxn];
void add1(int u, int v, int w)
{e1[++num1].w = w;
    e1[num1].to = v;
    e1[num1].nt = h1[u];
    h1[u] = num1;
}
void add2(int v, int u, int w)
{e2[++num2].w = w;
    e2[num2].to = v;
    e2[num2].nt = h2[u];
    h2[u] = num2;
}
typedef pairP;
//反向建边dj  T->S
void dj()
{memset(dis, 0x3f, sizeof(dis));
    dis[E] = 0;
    priority_queue, greater
>q;
    q.push(make_pair(dis[E], E));
    while (!q.empty())
    {P p = q.top();
        q.pop();
        int u = p.second;
        int diss = p.first;
        if (vis1[u])continue;
        vis1[u] = 1;
        for (int i = h2[u]; i; i = e2[i].nt)
        {int v = e2[i].to;
            if (dis[v] >diss + e2[i].w)
            {dis[v] = diss + e2[i].w;
                q.push(make_pair(dis[v], v));
            }
        }
    }
}
typedef pairPP;
int A_start()
{if (dis[S] >= 0x3f3f3f3f)return -1;
    priority_queue, greater>q;
    q.push(make_pair(dis[S], make_pair(0, S)));
    int cnt = 0;
    while (!q.empty())
    {PP p = q.top();
        q.pop();
        int u = p.second.second;
        int diss = p.second.first;
        if (u == E)cnt++;
        if (cnt == K)return diss;
        for (int i = h1[u]; i; i = e1[i].nt)
        {int v = e1[i].to;
            q.push(make_pair(diss + e1[i].w + dis[v], make_pair(diss + e1[i].w, v)));
        }
    }
    return -1;
}

void init() {num1 = num2 = 0;
    memset(vis1, 0, sizeof vis1);
    memset(h1, 0, sizeof h1);
    memset(h2, 0, sizeof h2);
}
signed main()
{ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (cin >>n >>m) {init();
        cin >>S >>E >>K >>T;
        if (S == E)K++;
        while (m--)
        {int u, v, w;
            cin >>u >>v >>w;
            add1(u, v, w);
            add2(u, v, w);
        }
        dj();
        int ans = A_start();
        if (ans == -1 || ans >T)cout<< "Whitesnake!\n";
        else cout<< "yareyaredawa\n";
    }

    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享题目：数据结构以及图论补充-创新互联
标题URL：http://lszwz.com/article/jgcgh.html