如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案....../ T0 i5 O6 f9 m- T7 E$ J

) K( [7 N+ Q# i    在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量，这就非常简单。但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......
) F% u8 v) `+ W+ R1 R5 I: t
( V8 A3 i/ }, e    基本的方式
' K1 o/ V; n3 k4 f" S3 C* {
. ]6 s5 {3 m' r# N7 o- c    构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：
, \$ E6 |! ^  W7 A' F' ]* [
! ^5 k8 d7 F" v( Z4 Z  H    tokenHolder.segmentStart=segmentSize;3 b6 P/ h5 }6 y/ o) x

/ Z7 ?0 D" R7 W2 s$ n- o6 d# P$ O    segmentSize+=_stake;! w2 c1 v1 ]3 x( S# Z1 t" U

9 p) _9 L1 Z! ?" a* B    tokenHolder.segmentEnd=segmentSize;
2 t  V& f4 B. l2 H1 F& S* f1 {  u
* J4 ~' P1 W3 V9 v, B    这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。
- k+ F2 C2 i  y  k9 Z) k. Q) n
# Z4 T; @$ T+ A0 T9 B7 K3 S0 {    首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。3 ^5 p) L$ N& W7 g$ ?! z

8 C1 `: t/ S$ I8 D; G  z' n5 Y    其次，获得被抽中者需要迭代每位持有者，如下所示：, T8 U9 C. }' n- c; {/ O+ G- I
* m' J1 k/ X/ g5 C0 P' i# [5 ~2 s
    //O(n)wherenisthenumberoftokenholderswithstake
, s6 Q0 z( D# I$ J0 `
- O1 U" ?# Z* G+ ]    for(uinti=0;i; Y# r- u, J+ k: U, T: S% S
; ~. U8 o4 c& w, V- Z
    if(currentDrawnNumber.segmentEnd)* i$ {& N- b- A" K8 h! P+ Q1 D9 ^

1 C* b: ^+ y: G7 Y  `    returntokenHolders.address
7 ~0 ~2 O) W; P) [$ i1 \
( e8 ^5 n& X: H% f/ f  R    在任何规模可观的系统中，每次抽奖都会需要很多算力。这种算法还制造了O（d*a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。; P$ o  q3 P9 N% L4 k: K
$ O, ~# v% U2 g4 \+ `
    树状数组解决方案  p  t6 j3 ^9 {5 t% D

: ~/ ~9 w/ h9 t  c8 T4 g% [    在寻求更好的方法过程中，我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组（K=2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：4 E, V, g+ U7 M" q0 M

2 _* t. U: Z0 P* _5 N    二进制树状数组示例
6 o; K. E0 u4 d5 D8 f8 @$ v2 o% o& ?, _( I: q1 A% i
    在以上示例中，假设我们抽取到数字13，寻取方式如下：首先13落在[0-24,25-49]的哪个区？0-24，所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。, M' g# l  z( L! p' T4 P4 T& G) j
9 C- M8 C$ ^+ v% X( v
    现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。) k6 _: Y0 L( `1 h* a

: y7 Z9 r+ x5 c" V' p! b' d    所以这个数据结构让我们的抽取复杂度变为O（K*log（n）/log（K）），其中K是每个节点的子节点数。log（n）/log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。
2 r! Y( l# a0 |: p/ \9 w! o8 o: G% y
    设置，删除和追加的复杂度都是O（log（n）/log（K）），因为是从给定的数据节点开始，逐级向上操作。注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现：
! k, s1 M" z* o3 `, j( {$ Z: h! M% m/ h" U( o4 k
    设置：设置新值并更新根值。
  x! b; C+ ~5 \* o5 Y& h0 _8 k; p- F* ?0 x( m$ @, v2 t5 U$ C9 |2 l0 i
    删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。
2 H8 s/ s! A8 n- J
. O& v3 K: o8 e! c- R) J    追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。( Y7 k: |+ Q) Y7 S( A  t3 a

6 M! `' R) d3 M6 X1 }    执行过程中的算力节省
  O* ~3 j) t- C+ Q% J0 u9 }! b: P" B
    因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示，列表会是：[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历：
2 b3 [, B$ x0 Z6 |7 s2 T2 i8 e% X/ V' D# r0 D/ `2 u3 F$ S, Z
    节点i的第C个子节点：K*i+c。原理：首先必须跳过每个i之前的节点的和它们的子节点，所以是K*i；然后加上c来得到你想要的子节点。
, K. i" ~2 W  s7 u$ n3 w, q" E( r# b, @/ \/ n3 V
    节点i的根节点：（i-1）/K。原理：跳过多少个拥有K个子节点的节点才能到达i。
2 S1 t- H2 e& N0 P6 H
- G  b( p% P2 V" }    检查节点i是否是第一个/最左边的节点：（i-1）％K===0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。
) p8 y. T3 e9 W2 |# U* x. |0 w3 Z6 d8 |# |, S
    Kleros的实例% B! m, J. K, |6 m

. t* v* z8 Z4 |, G3 L    Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros ... cts/data-structures
$ K" ^5 u$ Q0 j  y& p/ g: a% Y6 ~% y6 Y
    里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。