树状数组如何修改区间的值
发布网友
发布时间：2022-04-24 20:53
共3个回答
热心网友
时间：2022-05-04 21:17
区间最小值：如果是单端点（从1到r）或者是 双端点（l和r)但是静态的就可以，双端点lg^2 n，原理是区间*近
你也可以在树桩数组里实现lazy-tag，就是不一般的麻烦，我还没调过
Code:（我写麻烦了）
修改整个区间的值（一维度）：
#include <cstdio>
#include <cstring>
using namespace std;
int n,c[1000005];
void chg_org(int i,int delta) {
while (i<=n) {
c[i]+=delta;
i+=i&(-i);
}
}
int qry_org(int i) {
int ret=0;
while (i>0) {
ret+=c[i];
i-=i&(-i);
}
return ret;
}
void chg_itvl(int l,int r) {
chg_org(l,1);
chg_org(r+1,-1);
}
int qry_elem(int x) {
return qry_org(x);
}
int main() { //a sample:p2155,1-dimension
scanf("%d",&n);
memset(c,0,sizeof c);
int m,k,xx;
scanf("%d",&m);
for (int i=0;i<m;++i) {
scanf("%d%d",&k,&xx);
if (k>0)
chg_itvl(k,xx);
else
printf("%d\n",qry_elem(xx)%2);
}
return 0;
}
区间最小值：我把它和传统的方在一起了
{
the insert,query_sum function are for sum,they work dynamically.
the prep_rmq,query_min function are for rmq,they work statically only.
}
var
sum:array [1..10000000] of int64;
min:array [1..10000000] of longint;//only static avaliable
a:array [1..10000000] of longint;
n,i,t,m,q1,q2,l,r:longint;
procere insert(i:longint;key:longint);
//only maintain the sum field
var dx:longint;
begin
dx:=key-a[i];
a[i]:=key;
while (i<=n) do
begin
inc(sum[i],dx);
inc(i,i and (-i));
end;
end;
function query_sum(i:longint):int64;
begin
query_sum:=0;
while (i>0) do
begin
inc(query_sum,sum[i]);
dec(i,i and (-i));
end;
end;
function _min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
procere prep_rmq;
var
i,k,j:longint;
begin
for i:=1 to n do
begin
min[i]:=a[i];
k:=i and (-i);
j:=1;
while (j<k) do
begin
min[i]:=_min(min[i],min[i-j]);
j:=j shl 1;
end;
end;
end;
function query_min(l,r:longint):longint;
begin
query_min:=maxlongint;
repeat
while r-(r and (-r))>=l do
begin
query_min:=_min(query_min,min[r]);
dec(r,r and (-r));
end;
if r<l then break;
query_min:=_min(query_min,a[r]);
dec(r);
until r<l;
end;
begin
readln(n,q1,m,q2);
for i:=1 to n do
begin
read(t);
insert(i,t);
end;
prep_rmq;
for i:=1 to q1 do
begin
readln(l,r);
writeln(query_min(l,r));
end;
for i:=1 to m do
begin
read(q1,t);
insert(q1,t);
end;
for i:=1 to q2 do
begin
readln(t);
writeln(query_sum(t));
end;
end.
看不懂动手单步一下，原理是很清晰的。
另外,站长团上有产品团购,便宜有保证
热心网友
时间：2022-05-04 22:35
而查询区间可以修改后变为修改区间 你想想 就明白了
