如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案......0 @7 J3 X+ X* v5 j* U" f. I
5 l4 J0 X% A/ R" B  {1 {2 p
    在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量，这就非常简单。但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......
2 t) j, `6 @2 E8 e& E5 B0 C# q7 q) l
    基本的方式
! b5 \  e& `& Q+ }, H: @
# R; e' F  ]" z& o" O9 g  d* r    构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：
; t' U! z+ F$ N: N3 X9 r" o' B, m% R0 t
    tokenHolder.segmentStart=segmentSize;
$ M: I1 |; J- i% ^3 V; `7 {" O% t& l: _/ H+ G) ~
    segmentSize+=_stake;% y: F3 E5 L) B7 B% r
+ J" h$ L: _+ c, o1 B4 n  f
    tokenHolder.segmentEnd=segmentSize;
! y% t7 v* q, G, \
  x) s/ ]0 G; G( I6 k3 [% v    这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。
( H  }- C, J/ S; N8 `& ]
& [: x: ~# n' |7 B    首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。% P+ O4 F3 Y  H* v* w

* j; m! a% m/ V* R& c1 d  b    其次，获得被抽中者需要迭代每位持有者，如下所示：4 k. ?: N+ J" @

2 z$ E+ b4 o# t! y# U    //O(n)wherenisthenumberoftokenholderswithstake
2 V. y& \7 s9 k1 V" p% C+ [. |- z& G8 m5 V+ L$ ?) {" w% j
    for(uinti=0;i
  d7 g) Z1 }) I# F+ h- P
* P5 G$ F7 W0 e0 J3 R    if(currentDrawnNumber.segmentEnd)2 o) X' Z) m7 {- X$ D

# A3 P0 x# m" f/ m- r5 w5 l    returntokenHolders.address0 k/ g0 E) n4 L$ {3 R8 m
: f9 o, w5 u9 c: |. j1 |- C
    在任何规模可观的系统中，每次抽奖都会需要很多算力。这种算法还制造了O（d*a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。8 b& R' ?0 n, _9 a4 R

" Y0 U  V3 d/ {    树状数组解决方案
' Z( n  B  C8 q: Z; Z5 W4 |% X, B4 i9 F8 J: S
    在寻求更好的方法过程中，我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组（K=2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：, f, k! M6 ~+ E1 `6 ?5 U* Q

2 @  L5 x# e( O5 @    二进制树状数组示例1 q2 \! }, l! ]2 H3 J4 q9 b  y

1 ~' o. D! D9 X/ F) u! s( w    在以上示例中，假设我们抽取到数字13，寻取方式如下：首先13落在[0-24,25-49]的哪个区？0-24，所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。
% ^. ~% h' F* q1 L0 \5 j: }7 e
1 J: H# f3 U5 C    现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。
' m& n# D) e" d0 q9 s% A, u5 `- Z* {
& N; o* V1 [+ j' J% {. z    所以这个数据结构让我们的抽取复杂度变为O（K*log（n）/log（K）），其中K是每个节点的子节点数。log（n）/log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。/ B& I4 e, \# _5 e, B  P! `

2 j! P% \( \. [1 |' Q. A2 o    设置，删除和追加的复杂度都是O（log（n）/log（K）），因为是从给定的数据节点开始，逐级向上操作。注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现：
$ ]* j, G' t' c6 N7 D5 k' j, g* O1 x3 v9 V
    设置：设置新值并更新根值。
3 ^+ B, H* H3 T1 D, \9 k  }5 p, y3 @: Y  c
    删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。
; j1 c9 V: o. h) D5 P; t% a) C" n
1 S  @4 k" ?1 S2 T; T0 y8 X    追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。
0 E, q5 x, J8 |9 x3 N2 T( Y+ ?
: u/ o* w6 q, i3 R7 z. W+ S+ [( J    执行过程中的算力节省
4 L# w3 Q) o/ p8 g! R+ v3 u* x5 v/ }; N( l6 I
    因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示，列表会是：[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历：. L( [3 c' I2 v. y/ \5 ?) I5 J

) y4 T1 O, j/ I4 J% F    节点i的第C个子节点：K*i+c。原理：首先必须跳过每个i之前的节点的和它们的子节点，所以是K*i；然后加上c来得到你想要的子节点。
) q; ~! B( R7 U9 l! {; w+ `
( W) X  }% H8 P1 P; R4 k/ F    节点i的根节点：（i-1）/K。原理：跳过多少个拥有K个子节点的节点才能到达i。
1 I  s4 E' J9 O" h- T+ Q' K+ }, a9 d" f" L1 k1 ^; N9 F: j  U
    检查节点i是否是第一个/最左边的节点：（i-1）％K===0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。
7 `7 T5 q$ J! j" _( v6 |6 G" |2 C9 M0 \3 o  H, o$ S5 w
    Kleros的实例2 z& q, q# L0 @4 T
0 ~: g$ F. @. }
    Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros ... cts/data-structures! T, |# W+ l  t3 J. a0 ^0 h$ ~
1 [" f7 j- u# `. D+ ]5 ]3 R& Z
    里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。