模板【树状数组】【线段树】【最大子段和】

树状数组：

int bit[MAXN],n,a[MAXN];
int lowbit(int x) {
	return x&(-x);
}
void add(int i,int x) {
	while(i<=n) {
		bit[i]+=x;
		i+=lowbit(i);
	}
}
int sum(int i) {
	int s=0;
	while(i>0) {
		s+=bit[i];
		i-=lowbit(i);
	}
	return s;
}
int main() {
	scanf("%d",&n);
	memset(bit,0,sizeof bit);
	for(int i=1; i<=n; i++) {
		scanf("%d",&a[i]);
		add(i,a[i]);
	}
	/*
	查询 u 到 v的和 
	*/ 
	int ans = sum(v) - sum(u-1);
	return 0;
}

线段树：

/*线段数模板*/
maxn -> 最多节点数
struct node {
	int l,r;
	ll sum,lazy;
} tree[maxn * 4]; // 开四倍大小

void push_up(int root) {
	tree[root].sum = tree[root << 1].sum + tree[(root << 1) | 1].sum;
}   // 儿子的值相加为父亲的值

void push_down(int root) {
	if(tree[root].lazy) { //有懒惰值
		tree[root << 1].lazy += tree[root].lazy;
		tree[(root << 1) | 1].lazy += tree[root].lazy;//向下传递懒惰值
		tree[root << 1].sum += tree[root].lazy * (tree[root << 1].r - tree[root << 1].l + 1);
		tree[(root << 1) | 1].sum += tree[root].lazy * (tree[(root << 1) | 1].r - tree[(root << 1) | 1].l + 1); //根据题目要求处理
		tree[root].lazy = 0;
	}
}

void build_tree(int l,int r,int root) {
	tree[root].lazy = 0;
	tree[root].l = l;
	tree[root].r = r;
	if(l == r) {
		tree[root].sum = 0; // 这里给一个初始值
		return ;
	}
	int mid = (l + r) >> 1;
	build_tree(l,mid,root << 1);
	build_tree(mid + 1,r,(root << 1) | 1);
	push_up(root); //向上更新值
}
//区间l到r  每个点加v 
void update_interval(int l,int r,int v,int root) { //区间更新
	if(l <= tree[root].l && r >= tree[root].r) {
		tree[root].lazy += v; // 保存懒惰值
		tree[root].sum += v * (tree[root].r - tree[root].l + 1);
		return ;
	}
	if(tree[root].lazy)
		push_down(root);
	int mid = (tree[root].l + tree[root].r) >> 1;
	if(l <= mid)
		update_interval(l,r,v,root << 1);
	if(r > mid)
		update_interval(l,r,v,(root << 1) | 1);
	push_up(root);
}

int query_interval(int l,int r,int root) { // 区间查询
	if(l <= tree[root].l && r >= tree[root].r)
		return tree[root].sum;
	if(tree[root].lazy) // 查询中遇到未更新的值，进行更新
		push_down(root);
	int mid = (tree[root].l + tree[root].r) >> 1;
	int ans = 0;
	if(l <= mid)
		ans += query_interval(l,r,root << 1);
	if(r > mid)
		ans += query_interval(l,r,(root << 1) | 1);
	return ans;
}
//点p直接赋值为v 
void update_single(int p,int v,int root) { //单点更新
	if(tree[root].l == tree[root].r && tree[root].r == p) {
		tree[root].sum = v;
		return ;
	}
	int mid = (tree[root].l + tree[root].r) >> 1;
	if(p <= mid)
		update_single(p,v,root << 1);
	else
		update_single(p,v,(root << 1) | 1);
	push_up(root);  //每个点更新都要向上更新值
}
int query_single(int p,int root) { //单点查询
	if(tree[root].l == tree[root].r && tree[root].r == p) {
		return tree[root].sum;
	}
	if(tree[root].lazy)
		push_down(root);
	int mid = (tree[root].l + tree[root].r) >> 1;
	if(p <= mid)
		query_single(p,root << 1);
	else
		query_single(p,(root << 1) | 1);
}

线段树（维护最大子段和）：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=50000+50;
int n,m,a[maxn];
struct node {
	int sum;//区间和 
	int max_sum;//最大子段和 
	int max_pre;//最大前缀和 
	int max_post;//最大后缀和 
} t[maxn<<2];
void pushup(int rt) {//向上传递 
	int ls=rt<<1,rs=rt<<1|1;
	t[rt].sum = t[ls].sum+t[rs].sum;
	t[rt].max_sum = max(max(t[ls].max_sum,t[rs].max_sum),t[ls].max_post+t[rs].max_pre);
	t[rt].max_pre = max(t[ls].max_pre,t[ls].sum+t[rs].max_pre);
	t[rt].max_post = max(t[rs].max_post,t[rs].sum+t[ls].max_post);
}
void build(int rt,int l,int r) {
	if(l==r) {
		t[rt].max_sum=t[rt].max_pre=t[rt].max_post=t[rt].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pushup(rt);
}
node query(int rt,int l,int r,int ql,int qr) {
	if(ql<=l&&r<=qr)
		return t[rt];
	int mid=(l+r)>>1;
	if(qr<=mid)
		return query(rt<<1,l,mid,ql,qr);
	else if(ql>mid)
		return query(rt<<1|1,mid+1,r,ql,qr);
	else {
		node ans,ls=query(rt<<1,l,mid,ql,qr),rs=query(rt<<1|1,mid+1,r,ql,qr);
		ans.sum=ls.sum+rs.sum;
		ans.max_sum=max(max(ls.max_sum,rs.max_sum),ls.max_post+rs.max_pre);
		ans.max_pre=max(ls.max_pre,ls.sum+rs.max_pre);
		ans.max_post=max(rs.max_post,rs.sum+ls.max_post);
		return ans;
	}
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	scanf("%d",&m);
	while(m--) {
		int x,y;
		scanf("%d %d",&x,&y);
		printf("%d\n",query(1,1,n,x,y).max_sum);
	}
	return 0;
}