如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案......
4 `1 w2 O6 K  o: P
  y) Y% U" R: U5 E. _# Z$ D! z    在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量，这就非常简单。但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......
' w" r! N8 f' H$ |8 J" C
6 W/ S5 K4 S, c    基本的方式
9 G% f* h( w" S  t  w
" p& P1 k' H4 D& z0 Y    构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：# t3 Z1 ]( v4 h- L* B
0 Q4 |, j2 B5 D; w
    tokenHolder.segmentStart=segmentSize;
3 ~. P% L2 S5 b; N4 ~' E, _% ]9 A* S/ y1 G  I+ {- a, \8 `6 W0 e- U; m
    segmentSize+=_stake;0 r2 R& B$ `0 q* I8 I: w, v

5 M" y; c6 b8 b    tokenHolder.segmentEnd=segmentSize;1 {8 ~5 W4 K! O% C/ B
* k) K) N2 D' O% y
    这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。
. C3 R4 j/ v- U( e" A1 q
5 V# t9 Q2 @  T  s    首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。
  i* P/ L9 a; d- d7 d- m, F9 j3 P$ f# U3 X
    其次，获得被抽中者需要迭代每位持有者，如下所示：
. P: R* |1 f  ?6 [0 q# D2 ]* K5 A
    //O(n)wherenisthenumberoftokenholderswithstake3 {& o7 a2 v' Y  r
8 k$ ^( ?8 B- X  H$ I! A
    for(uinti=0;i
$ x# {& e; F. ^; p2 m0 K. P. y7 z: ]' v9 w2 c
    if(currentDrawnNumber.segmentEnd)
6 \2 O% w% S# P) i$ V" S
* p% ]6 m1 d' k5 Y    returntokenHolders.address& E2 R: o9 k' d0 h- ^0 E

* \, K8 n( N) H, s) m    在任何规模可观的系统中，每次抽奖都会需要很多算力。这种算法还制造了O（d*a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。6 m- X6 N3 q9 P9 o7 u, O$ w

: |$ |: k7 A3 w3 p( e" ~0 H    树状数组解决方案3 S' Q0 F! Z) e" S5 `

0 N$ K4 A# C' E( i    在寻求更好的方法过程中，我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组（K=2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：
3 K$ W3 w( J! S, J0 z' Q: v% W% N, ?9 v6 t/ [
    二进制树状数组示例
2 f- F# j, F$ Q6 }, ]) G& S. y+ O$ ~! {9 b' j% R
    在以上示例中，假设我们抽取到数字13，寻取方式如下：首先13落在[0-24,25-49]的哪个区？0-24，所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。
+ J$ ^) A! _3 b) `9 M1 m9 Z" z4 z" J2 j9 m+ r5 s
    现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。1 x) F  S  ^* w4 P) ^+ ?. R
. r! D+ ]% b/ N% F3 W2 w/ f
    所以这个数据结构让我们的抽取复杂度变为O（K*log（n）/log（K）），其中K是每个节点的子节点数。log（n）/log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。
/ Q1 S( i2 W* h6 j: H# V8 I9 o1 i( U* P
    设置，删除和追加的复杂度都是O（log（n）/log（K）），因为是从给定的数据节点开始，逐级向上操作。注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现：
6 @, k5 B) ?# V. W6 l0 T) s! R) H1 x
    设置：设置新值并更新根值。; b( Z% W  ?) B/ X1 R' i- s" [7 n

4 G  I8 N% w/ s6 I& ]* J! h    删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。, l& e% g) X5 A7 n5 G- f
9 b0 N% U- M8 R9 F5 ^  h) F" j
    追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。4 m* X, V  S# h( P2 @6 ^* R7 O

% }1 O* [/ g8 V  O1 J& Y* q- j2 e    执行过程中的算力节省
, p; s' o  f' F( p# k. t( k2 V
: y2 d! S  G5 g/ O    因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示，列表会是：[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历：& @) w: y' g7 s$ X9 `
" G- d1 h7 ~! w* T4 D( k
    节点i的第C个子节点：K*i+c。原理：首先必须跳过每个i之前的节点的和它们的子节点，所以是K*i；然后加上c来得到你想要的子节点。9 _, o7 J6 X' x2 D. X

: S" x0 W0 A1 r- c& [    节点i的根节点：（i-1）/K。原理：跳过多少个拥有K个子节点的节点才能到达i。
4 T. q/ _$ q7 B8 U
; B* a4 P3 ]! M6 h/ C# g! N5 R    检查节点i是否是第一个/最左边的节点：（i-1）％K===0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。
0 y5 V6 O1 {& q' C( T( X0 T; x$ I$ B8 ?$ E
    Kleros的实例+ b( W0 h9 r/ Z5 j8 I" h

$ x# ^0 O# _! `# R7 \4 R+ I# L: r    Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros ... cts/data-structures
2 ]5 f6 |1 H6 E/ l
; ^& z5 _- [* X4 E' p1 b9 R2 p    里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。