//每天整理一点，太多了
https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html#4175712（ORZ）
POJ 3468 板子题 注意下数据范围 （因为int会爆，以后一定好好看题，浪费我10min....）
http://poj.org/problem?id=3468
#include<iostream>//线段树题目集
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 4e5 + 15;
typedef long long ll;
typedef struct
{
ll l,r,sum,f;//sum为区间和,f为懒人标记
}node;
node Tree[maxn];//线段树
ll n,q;
ll _left,_right,value;
void buildTree(int l,int r,int cur)
{
Tree[cur].l = l;
Tree[cur].r = r;//左右区间范围
if(l==r)
{
scanf("%lld",&Tree[cur].sum);
return;
}
int mid = (l + r) >> 1;
buildTree(l,mid,cur*2);
buildTree(mid+1,r,cur<<1|1);
Tree[cur].sum = Tree[cur<<1].sum + Tree[cur<<1|1].sum;
}//建树
void Down(int cur)
{
Tree[2*cur].f += Tree[cur].f;
Tree[2*cur+1].f += Tree[cur].f;
Tree[2*cur].sum += (Tree[2*cur].r - Tree[2*cur].l + 1)*Tree[cur].f;
Tree[2*cur+1].sum += (Tree[2*cur+1].r - Tree[2*cur+1].l + 1)*Tree[cur].f;
Tree[cur].f = 0;//因为已经传下去了,所以清零
}//懒标记下传
ll ans;
void ask_interval(int cur)
{
if(_left<=Tree[cur].l&&Tree[cur].r<=_right)
{
ans += Tree[cur].sum;
return;
}
if(Tree[cur].f)
Down(cur);//下传懒人标记
ll mid = (Tree[cur].l + Tree[cur].r) >> 1;//mid 中间值
if(_left<=mid)
ask_interval(cur<<1);
if(_right>mid)
ask_interval(cur<<1|1);
}
void change_interval(int cur)
{
if(_left<=Tree[cur].l&&Tree[cur].r<=_right)//if node 在区间范围内
{
Tree[cur].sum += (Tree[cur].r - Tree[cur].l + 1)*value;
Tree[cur].f += value;
return;
}
if(Tree[cur].f)
Down(cur);
ll mid = (Tree[cur].l + Tree[cur].r) >> 1;//mid 中间值
if(_left<=mid)
change_interval(cur<<1);
if(_right>mid)
change_interval(cur<<1|1);
Tree[cur].sum = Tree[cur<<1].sum + Tree[cur<<1|1].sum;//(important) 更新完后一定要更新sum的总和值
}//线段树区间修改
int main()
{
while(scanf("%lld%lld",&n,&q)==2)//写返回值,不然可能会有些很SB的output 超出limit
{
memset(Tree,0,sizeof(Tree));
buildTree(1,n,1);//1 ~ n为范围,cur 为当前节点
char cmd;
while(q--)
{
ans = 0;
getchar();
scanf("%c",&cmd);//区间查询,区间修改
scanf("%lld%lld",&_left,&_right);
if(cmd=='Q')
{
ask_interval(1);
cout<<ans<<endl;
}else{
scanf("%lld",&value);
change_interval(1);
}
}
}
}
线段树 GSS1（求静态最大连续子段和）
（挺简单的，看代码就好了）
附个题目链接http://codevs.cn/problem/3981/
#include<bits/stdc++.h>//线段树求GSS1(最长子区间范围)
using namespace std;//主要同于解决求每一个区间范围内的最大连续子串
const int maxn = 2e5 + 32;
typedef long long i64;//GSS1 1.全在左子树上 2.全在右子树上 3.左右连续区间都存在
template <typename T>
void read(T &x)
{
x=0; int f=1; char c=getchar();
while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
x*=f;
}
void out(i64 ans)
{
if(ans<0) { putchar('-'); ans=-ans;}
char s[20]; int len=0;
do s[++len]=ans%10+'0'; while(ans/=10);
while(len) putchar(s[len--]); putchar('
');
}
struct Node
{
i64 sum,lmx,rmx,mx;//sum为区间和，lmx最大左连续区间和，rmx最大右连续区间和,mx最大区间连续值
void clear()
{
sum = lmx = rmx = mx = 0;
}
}Tree[4*maxn+1];
typedef struct Node nd;
void build_Tree(int node,int l,int r)
{
if(l==r)
{
read(Tree[node].mx);
Tree[node].lmx = Tree[node].rmx = Tree[node].sum = Tree[node].mx;
return;
}
int mid = (l + r) >> 1;
build_Tree(node<<1,l,mid);
build_Tree(node<<1|1,mid+1,r);
Tree[node].mx = max(Tree[node<<1].mx,Tree[node<<1|1].mx);
Tree[node].mx = max(Tree[node].mx,Tree[node<<1].rmx + Tree[node<<1|1].lmx);
Tree[node].lmx = max(Tree[node<<1].lmx,Tree[node<<1].sum+Tree[node<<1|1].lmx);
Tree[node].rmx = max(Tree[node<<1|1].rmx,Tree[node<<1|1].sum + Tree[node<<1].rmx);
Tree[node].sum = Tree[node<<1].sum + Tree[node<<1|1].sum;
}
int n,m,l,r;
nd query(int node,int left,int right)
{
if(l<=left&&right<=r)
return Tree[node];
int mid = (left + right) >> 1;
if(r<=mid)
return query(node<<1,left,mid);//全在左范围区间
if(l>mid)
return query(node<<1|1,mid+1,right);
//(important) 和求区间和的板子有所不同,因为可能存在1 ~ 7这种线段树中本身不存在的node,因此需要
//在左右区间都有的情况下分离出来,创造新节点并返回
//左右区间都有
nd lchild; lchild.clear();
lchild = query(node<<1,left,mid);
nd rchild; rchild.clear();
rchild = query(node<<1|1,mid+1,right);
nd parent; parent.clear();
parent.mx = max(lchild.mx,rchild.mx);
parent.mx = max(parent.mx,lchild.rmx+rchild.lmx);
parent.lmx = max(lchild.lmx,lchild.sum + rchild.lmx);
parent.rmx = max(rchild.rmx,rchild.sum + lchild.rmx);
parent.sum = lchild.sum + rchild.sum;
return parent;
}
int main()
{
read(n);
build_Tree(1,1,n);
read(m);
for(int i=0;i!=m;++i)
{
read(l);
read(r);
i64 answer = query(1,1,n).mx;
out(answer);
}
}