选修5 人工智能初步《第一单元 感受人工智能的魅力 第二节 畅游人工智能世界 机器翻译》优秀教案

选修5 人工智能初步《第一单元 感受人工智能的魅力 第二节 畅游人工智能世界 机器翻译》优秀教案

注意：线段树数组不能只开到2*n级别，要开到4*n级别。因为标号会超过2n，有时会爆空间。线段树要开4倍空间。

注：k为线段树的标号，le,ri为线段树的区间。

二、建树：

void build(int k,int le,int ri)

{

if(le==ri) sum[k]=a[le],return;

int mid=(le+ri)>>1;

build(k<<1,le,mid);

build(k<<1|1,mid+1,ri);

sum[k]=sum[k<<1]+sum[k<<1|1];

}

三、单点修改：

void change(int k,int le,int ri,int p,int v)

{

if(le==p&&le==ri)

{

sum[k]+=v;return;

}

int mid=(le+ri)>>1;

if(p<=mid) change(k<<1,le,mid,p,v);

else change(k<<1|1,mid+1,ri,p,v);

sum[k]=sum[k<<1]+sum[k<<1|1];

}

四、区间修改：

我们在修改数据的时候，有些数据不在这个区间，不用修改，只有在这个区间的数才更新，如果全搜索一遍，时间复杂度无法接受。这样我们引入标记，只有符合条件的才更新，让标记下传。把这个标记称为Lazy-Tag（懒标记）。