如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案......
$ C' R. B8 l5 M5 `  F" t1 p/ r- p3 B" H  w" M9 S" ?6 v
    在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量，这就非常简单。但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......
: M5 _5 \( N+ u9 u2 @' _+ z
, p9 O0 ^: ]- i9 b    基本的方式
: f, r; O6 g# h2 i% \5 p( n. ~0 h  L9 ?1 o: S; m" X) y# m
    构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：$ ^; L% n6 N" I3 l) l' ~
8 _7 T) S# t+ W. N  ]+ W7 T! u9 k
    tokenHolder.segmentStart=segmentSize;; \5 E/ T* ]! z. E" m% K, G

. y) e! b' w. Y& W2 p* `" n# a    segmentSize+=_stake;  X2 g6 i1 j# \! _

! ~1 w1 ^2 Y4 c- K6 F, |$ w    tokenHolder.segmentEnd=segmentSize;) _8 R; D+ b* Z6 A& u% J' P( t
( l9 q0 I% B; G" u! K6 `
    这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。
0 v! v* E: d5 r6 r, e& R8 L0 u0 t7 J+ A6 `# r0 V0 l% N( ^
    首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。# U- @+ q: ~& J3 r1 a
% Z: G0 ~5 E  X% s! {
    其次，获得被抽中者需要迭代每位持有者，如下所示：' `& h$ Y5 T5 S) m
; F7 |/ B, U. I" V) x3 G: S+ _
    //O(n)wherenisthenumberoftokenholderswithstake
# x" I9 j8 d3 ?6 q, d' f2 R8 y
0 [; Y7 Z& u9 E! m    for(uinti=0;i% f$ H9 U$ A* V8 E
; {# u% \1 U7 X+ O: ]( T( N
    if(currentDrawnNumber.segmentEnd)
2 o8 O( e1 y& \9 g+ T3 v' w, g7 l# k  [( }  d
    returntokenHolders.address
2 N, B7 y- T% [, p; H. w, s
: h2 C9 e2 j% n. x    在任何规模可观的系统中，每次抽奖都会需要很多算力。这种算法还制造了O（d*a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。; f0 g6 G+ X: Z" @
/ `+ Y  K9 e7 y2 Q! c9 q& K' f
    树状数组解决方案1 \5 n( D8 N9 b
1 Y  f: W7 r5 E5 }" l; }
    在寻求更好的方法过程中，我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组（K=2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：
% y9 @9 Z0 ?% z% ]! }% @& f; R% D0 q) y( ^7 z- F4 [" d# P3 y
    二进制树状数组示例
9 o; j$ |- y4 _4 z
: Q8 r7 ]2 u9 p, o    在以上示例中，假设我们抽取到数字13，寻取方式如下：首先13落在[0-24,25-49]的哪个区？0-24，所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。/ @& l! l8 O+ @( g" p2 f7 H
% ?" p$ n! l8 C6 D+ A1 c& t
    现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。
* G' N+ {1 g1 }# t2 k
- p* T) L& Q+ p2 {1 i# \  O: D    所以这个数据结构让我们的抽取复杂度变为O（K*log（n）/log（K）），其中K是每个节点的子节点数。log（n）/log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。+ g! I- r- E+ l4 @" Q$ u4 s

! ]5 F; F# z& u9 v    设置，删除和追加的复杂度都是O（log（n）/log（K）），因为是从给定的数据节点开始，逐级向上操作。注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现：# L7 h! e; {6 w0 z" W: ]

/ m: m2 [0 ]! {; D4 I    设置：设置新值并更新根值。
: ]) S0 ^, g! {0 V% S
# X; ^! L. _1 @3 [5 P" |" _    删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。
, e2 n# z. Z" v8 G; e$ t' s$ L& i+ Z  o& r- r0 r
    追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。
7 ?. |: d0 o+ {7 C% i5 s. _" \4 t. |5 T$ ?1 a
    执行过程中的算力节省5 w7 V8 \; e9 I% e5 ]; S

3 l# ~0 D) u  }    因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示，列表会是：[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历：9 a, ~/ w1 u2 a9 U4 g

9 F( u; E; }8 t( g( @( R$ _    节点i的第C个子节点：K*i+c。原理：首先必须跳过每个i之前的节点的和它们的子节点，所以是K*i；然后加上c来得到你想要的子节点。
% F/ E1 E: i* ]
1 m& }! X8 ]* I6 o/ B    节点i的根节点：（i-1）/K。原理：跳过多少个拥有K个子节点的节点才能到达i。
, [8 m- t! X& w5 V4 I: g3 U/ M* [0 @. r
    检查节点i是否是第一个/最左边的节点：（i-1）％K===0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。
* v+ o" e, k* L8 ~4 o, J6 K: d3 e7 N! I
    Kleros的实例
7 h: Z: a  f- q* j" ?( m& z1 v& F# e6 ]) ?: w% @
    Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros ... cts/data-structures* T' q( ?% l7 P+ I; r
% H+ ]* n7 A1 f  g' E! K9 e' P
    里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。