如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案......" z+ i& s/ {  h9 ^

9 M% V# B7 X; b; {' \, Y( j9 Z4 V- ~    在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量，这就非常简单。但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......0 D# @$ T2 D8 c1 a" E# ~# E7 ~

9 O1 K4 O% F( K! V! s8 Q5 D. x    基本的方式
, m9 q' V( k. D$ Z$ E6 D6 I! H% S% m9 P4 e/ S
    构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：
4 P' \) q5 S/ Q2 I* a! ]( d' [3 ^1 M) Z8 h- w0 o$ W
    tokenHolder.segmentStart=segmentSize;
, Y! X  @; [. ^9 Y6 Y' T, D9 _
- N7 w7 |" V+ k8 n    segmentSize+=_stake;
) i! P& }& m9 f9 V2 _$ R6 E' }% M) }0 E5 t2 v# t8 e6 T
    tokenHolder.segmentEnd=segmentSize;9 q' M* g9 ]2 w  D1 X
" K- U; Z( Y' d$ m" C
    这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。
/ e6 |, q! B; I& Z, p& O2 R/ U5 r5 Y, {5 o+ A
    首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。
* P2 O8 e6 m! b$ i- T' X
! F$ O7 [& ?: m! w: f    其次，获得被抽中者需要迭代每位持有者，如下所示：( Z5 @4 ~, m# k, f; t
' F8 b! L' Z, Z' I/ O
    //O(n)wherenisthenumberoftokenholderswithstake& K" h8 b. F' G* @: h) m: [
# K; `1 t! ?  j0 _6 z
    for(uinti=0;i9 ~: Y! Z8 O4 [/ u  L

* F* @  e  w8 A$ {3 f6 G    if(currentDrawnNumber.segmentEnd)$ b% R1 c; l2 @% n- n- N

7 m" ]! Z6 y* c. e+ D% J0 v" J5 X    returntokenHolders.address4 G3 ^- ?' ^0 f

9 F' {: `8 \, b2 k! H! y7 g1 ?    在任何规模可观的系统中，每次抽奖都会需要很多算力。这种算法还制造了O（d*a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。
- n4 l/ A" ?" E. z" }% e
& u# M4 C) [7 h* ?' @    树状数组解决方案( x% T  w! g/ a4 |

+ P+ z. y; J# A9 b    在寻求更好的方法过程中，我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组（K=2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：" }9 z4 n" ~( _4 @  Q6 X  ^* E# H
- s) a$ \1 H! `/ z
    二进制树状数组示例
* C, _4 C+ S# W9 l) T
; h* h) C+ T2 o# N) {    在以上示例中，假设我们抽取到数字13，寻取方式如下：首先13落在[0-24,25-49]的哪个区？0-24，所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。3 D( Z6 g& e$ a+ V$ }* S
+ S, ~0 h" ^* P- U- r
    现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。
. |+ h+ h# K6 k' O: M# N5 y- k+ I; j3 p0 F. [, I8 k" q9 U* V
    所以这个数据结构让我们的抽取复杂度变为O（K*log（n）/log（K）），其中K是每个节点的子节点数。log（n）/log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。, P4 `* @$ t) x+ I
/ X& L5 F) I* }2 `- Q( G: ^
    设置，删除和追加的复杂度都是O（log（n）/log（K）），因为是从给定的数据节点开始，逐级向上操作。注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现：+ K% G4 X2 ^# D# b; b
( S4 l  m/ J7 d! Z1 _
    设置：设置新值并更新根值。; U, \1 V; q- C5 l' `) `

+ ^, P7 v' ~! n% Y  g( e    删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。
+ [$ v3 T+ ~' p1 ]% R
0 h7 R' |2 V% ]  d    追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。) [: T: E  ?& \( h& ?$ J; j( N, C
" f5 ?" a, i8 l6 J1 F$ X
    执行过程中的算力节省0 Q8 o2 P5 ]8 r) ~' ?5 \( m
( S& v0 m8 _6 Z3 {/ x+ N8 I& j& P
    因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示，列表会是：[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历：
* i9 V6 T; b1 D0 ]# H/ T6 A3 V% N, B0 X6 v4 n
    节点i的第C个子节点：K*i+c。原理：首先必须跳过每个i之前的节点的和它们的子节点，所以是K*i；然后加上c来得到你想要的子节点。
) U4 {- \+ \& ^; R( _7 O6 p! i4 \
( D% i% ?9 x& A: x: c6 U    节点i的根节点：（i-1）/K。原理：跳过多少个拥有K个子节点的节点才能到达i。& ^( m, v7 ]* v

# ^  ]: ], L( g2 P+ ~* u4 V    检查节点i是否是第一个/最左边的节点：（i-1）％K===0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。$ K  J' `4 J* t$ e( b6 j7 q

- X6 p+ u. C" l( N8 k" C    Kleros的实例
/ N7 z4 Y  |: l5 H1 n. Q: N$ N8 _8 o; u4 k; O# i$ {+ x5 W9 |. X
    Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros ... cts/data-structures: d7 B' X% p" D/ M# A* ]- U
! c' ^; Q2 r# X9 n  `; d3 a
    里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。