如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案......
9 t$ M0 o( e0 c. ]+ u( e  ^- ?" Y, e! t! z" F# V
    在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量，这就非常简单。但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......
2 W0 U$ n0 b- M
" {9 U) c- w3 q+ X& \5 d9 O    基本的方式
' {0 u$ M/ V6 M6 |( C; z
# }. a* K7 V/ F( v+ H$ Z% _8 _5 L4 J    构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：( h0 u9 Z5 `0 _( v3 B# }1 n+ s8 r

+ A( ?7 G6 i( m    tokenHolder.segmentStart=segmentSize;
" ^2 a! H9 b4 ]4 Y, |+ U
& x+ e5 m8 w! p: D8 d    segmentSize+=_stake;8 G9 e4 ]7 E. [8 O. h9 R
5 X+ _4 O: z" j9 ?6 z; x( E+ h
    tokenHolder.segmentEnd=segmentSize;' o  l( A) c* r7 N1 l. R
! ^3 Q1 `" h* w2 x4 I
    这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。
6 r! }6 ^+ Q6 H, \& v% U) v% {2 Q7 ~0 W9 {
    首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。
& w5 m' n8 v' U" w7 f( m/ @
  G$ v7 M( X1 O6 Z# g! q    其次，获得被抽中者需要迭代每位持有者，如下所示：
0 p& @; Q8 \) |* m1 t" _. u9 N/ Z) b, z" g5 l
    //O(n)wherenisthenumberoftokenholderswithstake# R' A& A1 k% s/ Q  N

) }; C( s+ S: }  |! ]( g    for(uinti=0;i
$ }: t; h- h) [( E* C' y9 l7 A# z7 j+ I! u( J# p6 O8 s; G
    if(currentDrawnNumber.segmentEnd)
6 \; a/ i; n+ j, S  e* F+ i. u5 C  ^9 |
    returntokenHolders.address
7 z  [) g& h: q: n
8 d; i1 ^5 B' q2 a) a/ ?    在任何规模可观的系统中，每次抽奖都会需要很多算力。这种算法还制造了O（d*a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。' b+ G) x8 x8 P. r0 J
0 s9 U. L/ j% k$ S5 b9 V) {( @+ _
    树状数组解决方案
' b7 y5 j" g0 ^1 ^: e2 J4 g2 s8 k5 n# @6 S/ m7 l
    在寻求更好的方法过程中，我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组（K=2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：
) ^$ q6 h8 \- V' F6 o! E8 A
; ~  l4 V  M2 O. ^6 R" B    二进制树状数组示例9 G. m0 Y( U' p2 L7 Y4 ^% h* E

9 R. O9 u# ^6 B+ s    在以上示例中，假设我们抽取到数字13，寻取方式如下：首先13落在[0-24,25-49]的哪个区？0-24，所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。
* L  W7 v( w, ]5 Q
  h/ A7 t1 I* z% {    现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。
4 f+ N. K* S0 G% r7 A* H" H3 b% J" W" i2 G
    所以这个数据结构让我们的抽取复杂度变为O（K*log（n）/log（K）），其中K是每个节点的子节点数。log（n）/log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。; @: O; V8 h. s- s
$ l1 A% {5 V- j1 U4 e4 v
    设置，删除和追加的复杂度都是O（log（n）/log（K）），因为是从给定的数据节点开始，逐级向上操作。注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现：5 l! [$ r( S6 I# T
+ a/ d# V& V. k8 [% {1 u! O
    设置：设置新值并更新根值。
, u' n& ~( R2 U  d( D0 I! N- A& Q+ N. b/ A
    删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。
: ^9 S- Y; x! r; @
2 o9 ^6 \0 W/ I1 I    追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。
  x% Z! I& N7 S0 @8 X8 ?6 H9 a) r; q, S/ C4 K
    执行过程中的算力节省
. X' H2 y+ V- A
- o4 y4 s5 C8 u4 m0 j    因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示，列表会是：[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历：. U/ b0 O9 p  [) T, |1 `) P* f
) d0 y' N- ~3 E& A7 x
    节点i的第C个子节点：K*i+c。原理：首先必须跳过每个i之前的节点的和它们的子节点，所以是K*i；然后加上c来得到你想要的子节点。# L7 r; u" P: Y

2 \. Z1 P& m' e0 w7 D    节点i的根节点：（i-1）/K。原理：跳过多少个拥有K个子节点的节点才能到达i。) P, ^; l+ G& s7 `
7 \' ^1 p. E, D% T
    检查节点i是否是第一个/最左边的节点：（i-1）％K===0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。
( z6 t: F: V0 V6 c+ v7 E$ C) X# [( e! P2 ]' D3 X! d0 k# ^* r
    Kleros的实例
+ `8 h: e3 {' ^* G  P) R# V4 C  Y& T  T8 l7 b6 C6 r, \
    Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros ... cts/data-structures
: n% n8 ?" z+ Z% ?$ U) g( i- A9 L
    里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。