树状数组的其他功能
发布网友
发布时间：2022-04-21 21:06
共3个回答
热心网友
时间：2022-04-12 20:20
修改区间值可以，但是这样就不能求区间和了（只能求一个点），poj上的matrix是个很好的例子，代码在最后
区间最小值：如果是单端点（从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;
}
区间最小值：我把它和传统的方在一起了
{basic_structure->statistics->binary index tree}
{
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 int;
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):int;
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-04-12 21:38
应该是不可以的。
只能求出从1..k的最小值。
不过对于特殊的问题，可以通过改变添加次序来达到效果。
另对于区间问题存在一种括号法。即添加一段区间就相当于在左边添加一个左括号，在右边添加一个右括号，分别用两个树状数组来维护的话，会有很好的效果。对于二维问题，也有很多的支持（4个树状数组……）。具体请参加vijos《校门外的树》（注：不是noip那道…………笑~你懂得~~）vj爆了，去网上搜题解吧。
还有，如果你想用类似树状数组的位运算的方法得到这个算法。可以参考zkw的《统计的力量》。里面有很强的，自底向上线段树的内容。（和树状数组的实现思想有些类似）
