题目地址

Solution

前面已经知道了树状数组的单点修改和区间查询。这里利用差分的思想:具体来说,维护 \(b\) 数组:

\[b[i] = a[i]-a[i-1] \]

其中 \(a\) 为原来数组。可以发现

\[a[i] = \sum_{k=1}^ib[k] \]

因此我们只需要对 \(b\) 利用树状数组维护,get_sum[i]即可得到原来数组单点的值。而对于区间更新,我们只需要在两个端点 \(l,r\) 打上标记即可:

\[update(l,x);update(r+1,-x) \]

点击查看代码

int n,q;
const int N = 1e6+5;
ll a[N], b[N];
ll c[N];

ll lowbit(int x){return x&(-x);}

void update(int i, ll k){
    // add k on i-th position
    while(i<=N){
        c[i]+=ll(k); i+= lowbit(i);
    }
}
ll get_sum(int i){
    // get sum from 1-i
    ll ans = 0;
    while(i>0){
        ans+=ll(c[i]);i-=lowbit(i);
    }
    return ans;
}

int main(){
    //ios::sync_with_stdio(false);
    n = read();q = read();
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        b[i] = a[i]-a[i-1];
        update(i,b[i]);
    }
    while(q--){
        int tmp = read();
        if(tmp==1){
            int l=read(),r = read();
            ll x;scanf("%lld",&x);
            update(l,x);update(r+1,-x);
        }
        else{
            int pos = read();
            cout<<get_sum(pos)<<endl;
        }
    }
    
}

标签智能推荐:

设计模式之模板模式

模板模式的使用场景:当我们要完成在某一个细节层次一致的一个过程或一系列步骤,但其个别步骤在更详细的层次上的实现可能不同时,可以考虑用模板方法来处理。模板方法:在模板中,定义一个操作中算法的骨架(一般为重复的代码),而将一些步骤(不同的代码)&nbsp;“延迟”到子类中。模板方法使得子类可以不改变一个算法的结构即可重新定义该算法的某些特定的步骤。模板方法的优点:模板方法通过把不变行为搬移到超类(父类

自用代码模板

简介对于一些复用性较高的算法或者数据结构,需要时再重新实现一次是费时的,如果有一份设计得不错得代码模板,可能会花费更少的时间。在实现实现某个算法时,如果有类似算法的代码作为参考,可能效率会比较高。复习所学内容时,如果将已学内容的实现记录下来的话,可能会有更好的效果。基于以上目的,我自己会实现一些常见算法的代码模板。经过一段时间的完善,自认为写得还行,可能会有参考意义,所以也将这个代码模板开源了。模

L2TP:windows server 2008+:关于所用客户端证书的关键点说明

vpn客户端的证书的用法必须是:模板中的选项:二者(交换+签名)否则是无法建立L2TP连接的!更进一步,其实是ca进行发证时所选择的算法决定的:windowsserver2003的默认算法就是同时支持二者的。而,windowsserver2008+默认的算法竟然只是交换!!!!微软....无语了!

设计模式之模板方法

模板方法介绍模板方法模式是一种行为设计模式,它在超类中定义一个算法的框架,允许子类在不修改结构的情况下重写算法的特定步骤。模板方法模式建议将算法分解为一系列步骤,然后将这些步骤改为方法,最后在“模板方法”中依次调用这些方法。步骤可以是抽象的,也可以有一些默认的实现。为了能够使用算法,客户端需要自行提供子类并实现所有的抽象步骤(有时候还需要重写步骤)。模板方法将算法分解为步骤,并允许子类重写这些步骤

笔记整理

刷题记录我的资源C++/Java算法模板JS基础【未完成】大佬笔记前端[转载大佬高质量笔记]ES6-ES11笔记整理阮一峰ES6入门笔记HTML笔记CSS基础HTML5与CSS3

设计模式学习——模板方法模式

一、什么是模板方法模式模板方法模式:定义一个操作的算法的框架,将一些步骤延迟到子类中,从而使得子类在不改变整体算法结构的基础上即可重新定义该算法某些特点步骤。其类图如下:从类图我们可以看出来模板方法非常简单,它仅仅利用了继承机制,其中AbstractClass为抽象模板,他的方法分两类:基本方法基本方法也叫基本操作,是由子类实现的方法,并在模板方法中被调用。模板方法可以有一个或多个,其主要实现对基

衢州二中不被虐学习计划记录(选做)

一阶段初级(80题)基本算法枚举贪心分治法递推模拟法图算法图的深度优先遍历和广度优先遍历最短路径算法最小生成树算法拓扑排序二分图的最大匹配最大流的增广路算法数据结构串排序第一阶段初级(80题)基本算法枚举poj1753:直接dfspoj2965:直接dfs贪心poj1328:区间覆盖问题poj2109:通过位数确定答案的范围然后二分,注意用高精度poj2586:简单的贪心分治法poj1741:点分

模板方法模式

模板模式都是由抽象类来定义一个算法,在算法实现的不同步骤上抽象方法由子类继承并提供具体实现,常见的就是不同步骤提供doXXX抽象方法留给子类实现。模板模式一般有两部分组成,即抽象模板和具体模板。JDBCTemplate、RedisTemplate、MongoTemplate等均是典型的模板模式。publicabstractclassJdbcTemplate{//templatemethodpubl

Java 抽象类应用-抽象模板模式

模板方法模式(TemplateMethod):定义一个操作的算法骨架,将一些可变的部分延迟至子类中,模板方法模式可以使子类不改变算法的结构,而重新定义算法某些特定的步骤。publicclassAbstractModel{publicstaticvoidmain(String[]args){UserManagerum=newUserManager();um.action("admin","add")

设计模式之 模板方法模式

模板方法模式定义了一个算法框架,并通过继承的方式将算法的实现延迟到子类中,使得子类可以在不改变算法框架及流程的前提下重新定义改算法在某些环节的实现。(1)定义模板类publicabstractclassAbstractTemplate{privatefinalstaticLoglogger=LogFactory.getLog(this.getClass());publicvoidtemplateM