树状数组（Binary Indexed Tree,BIT）
转自大牛柳婼 の bloghttps://www.liuchuo.net/archives/2268
|
1
2
3
4
5
6
|
int
getsum
(
x
)
{
sum
=
0
;
for
i
;
>=
1
-=
lowbit
(
)
)
+=
c
[
i
]
;
return
sum
;
}
|
|
1
2
3
4
|
void
update
(
int
x
,
v
)
{
for
i
=
;
<=
n
+=
lowbit
(
)
)
c
[
i
]
;
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <cstdio>
#include <cstring>
const
maxn
10010
;
#define lowbit(i) ((i) & (-i))
maxn
;
void
update
,
v
{
<
)
]
;
}
{
;
)
@H_120_404@
;
;
}
main
(
{
n
;
scanf
(
"%d"
&
;
i
++
{
;
;
printf
"%d\n"
x
-
;
}
;
如果是求序列第k大的问题：可以用二分法查询第一个满足getsum(i) >= k的i@H_502_163@
|
