Segment tree & tree array template

Line tree template  

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#define fr(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=100005;
int n,q;
ll tree[4*maxn+1];
ll lz[4*maxn+1];
void build(int node,int l,int r)
{
	if(l==r)
	{
		scanf("%lld",&tree[node]);
		return;
	}
	int mid=(l+r)>>1;
	build(node*2,l,mid);
	build(node*2+1,mid+1,r);
	tree[node]=tree[node*2]+tree[node*2+1];
}
void update(int node,int l,int r,int index)
{
	if(l==r)
	{
		tree[node]=index;
		return;
	}
	int mid=(l+r)>>1;
	if(index<=mid)
		update(node*2,l,mid,index);
	else 
		update(node*2+1,mid+1,r,index);
	tree[node]=tree[node*2]+tree[node*2+1];
}
void push_down(int node,int l,int r)
{
	if(l==r)
	{
		lz[node]=0;
		return;
	}
	if(lz[node])
	{
		int mid=(l+r)>>1;
		tree[2*node]+=(mid-l+1)*lz[node];
		tree[2*node+1]+=(r-mid)*lz[node];
		lz[2*node]+=lz[node];
		lz[2*node+1]+=lz[node];
		lz[node]=0;
	}
}
void update_range(int node,int l,int r,int L,int R,int add)
{
	if(l>=L&&R>=r)
	{
		lz[node]+=add;
		tree[node]+=(r-l+1)*add;
		return;
	}
	push_down(node,l,r);
	int mid=(l+r)>>1;
	if(mid>=L)
		update_range(node*2,l,mid,L,R,add);
	if(mid<R)
		update_range(node*2+1,mid+1,r,L,R,add);
	tree[node]=tree[node*2]+tree[node*2+1];
}
ll query_range(int node,int l,int r,int L,int R)
{
	if(l>=L&&R>=r) return tree[node];
	push_down(node,l,r);
	int mid=(l+r)>>1;
	ll sum=0;
	if(mid>=L)
		sum+=query_range(node*2,l,mid,L,R);
	if(mid<R)
		sum+=query_range(node*2+1,mid+1,r,L,R);
	return sum;
}
int main()
{ 
//	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	build(1,1,n);
	memset(lz,0,sizeof(lz));
	return 0;
} 

  It's ridiculous to hit the board twice ......

 

Tree array template

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
const int maxn=500005;
int C[maxn];
int lowbit(int x)
{
	return (-x)&x;
} 
void insert(int i,int w)
{
	while(i<=n)
	{
		C[i]+=w;
		i+=lowbit(i);
	}
}
int query(int i)
{
	int sum=0;
	while(i>=1)
	{
		sum+=C[i];
		i-=lowbit(i);
	}
	return sum;
}
int main()
{
//	freopen("in.txt","r",stdin);
	
	return 0;
}

Sure enough, the tree array is easy to knock QAQ