题目描述
线段树
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
package com.rainco;
import java.util.*;
class Pos{
int l;
int r;
int sum;
int lazy; //懒标记的意义时该区间所有数都 +lazy 下传懒标记时候 每次访问左右儿子时候都要下传懒标记
// 不仅该节点要+值 (tr[p].lazy)*(tr[p<<1].r-tr[p<<1].l+1); lazy标记也要下穿
public Pos(int l, int r, int sum, int lazy) {
this.l = l;
this.r = r;
this.sum = sum;
this.lazy = lazy;
}
}
public class Main {
static int N=100010;
static int n;
static int m;
static Pos[]tr=new Pos[N*4];
static int[]A=new int[N];
static int get(int p){
return (p<<1)|1;
}
static void push_up(int p){
tr[p].sum=tr[p*2].sum+tr[get(p)].sum;
}
//懒标记在访问时 下传懒标记
static void push_down(int p){
if(tr[p].lazy!=0&&tr[p].l!=tr[p].r){
tr[p<<1].sum+=tr[p].lazy*(tr[p<<1].r-tr[p<<1].l+1);
tr[get(p)].sum+=tr[get(p)].lazy*(tr[get(p)].r-tr[get(p)].l+1);
tr[p<<1].lazy+=tr[p].lazy;
tr[get(p)].lazy+=tr[get(p)].lazy;
}
tr[p].lazy=0;
}
static void build(int u,int l,int r){
tr[u]=new Pos(l,r,0,0);
if(l>=r){
tr[u].sum=A[l];
return;
}
int mid=(l+r)/2;
build(u<<1,l,mid);
build(get(u),mid+1,r);
push_up(u);
}
//区间修改
static void update(int u,int l,int r,int v){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].sum+=(tr[u].r-tr[u].l+1)*v;
tr[u].lazy+=v;
return;
}
int mid=(tr[u].l+tr[u].r)>>1;
//System.out.println(tr[u].l+" "+tr[u].r+" "+l+" "+r);
push_down(u);
if(l<=mid){
update(u<<1,l,r,v);
}
if(mid<r){
update(get(u),l,r,v);
}
push_up(u);
}
static int query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u].sum;
}
int mid=(tr[u].l+tr[u].r)>>1;
int sum=0;
//System.out.println(tr[u].l+" "+tr[u].r+" "+l+" "+r);
push_down(u);
if(l<=mid){
sum+=query(u<<1,l,r);
}
if(mid<r){
sum+=query(get(u),l,r);
}
return sum;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
build(1,0,n);
for(int i=1;i<=n;i++){
int a=sc.nextInt();
A[i]=a;
update(1,i,i,a);
}
for(int i=1;i<=m;i++){
int k=sc.nextInt();
int a=sc.nextInt();
int b=sc.nextInt();
if(k==0){
System.out.println(query(1,0,b)-query(1,0,a-1));
}else{
update(1,a,a,b);
}
}
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla