如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案......5 a% w$ b, R* d) a( I7 i. f; H

3 X; D9 @+ K' }9 m    在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量，这就非常简单。但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......
! f3 m" Y7 z. D
, l, H/ }" [+ `3 h    基本的方式
# d  q9 V9 Q& \9 r; ^
2 X! l( Z' c' G1 x8 p6 A$ D8 A    构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：  z0 p0 D" i* Z9 g: q

! e* s9 d2 Y3 `* P/ a" ~: s. y) U    tokenHolder.segmentStart=segmentSize;5 G+ ?1 i6 g. G6 Q; \9 [
) R1 ?* W( Z; G$ Q! |% ~9 {+ m( Z
    segmentSize+=_stake;( _5 e( H% m  Z  y, g) E+ w9 _

6 m+ g. t, G( n' t$ v! H1 o0 v    tokenHolder.segmentEnd=segmentSize;1 k5 d9 M7 ^. h
0 u+ V; g" _, G9 {1 Q
    这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。: q. ^: t1 i# T" ^
& C. c7 [% J, V1 U
    首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。
3 J5 B) K2 n* w, w% f5 [
; A$ Y3 b4 F1 C6 z3 h    其次，获得被抽中者需要迭代每位持有者，如下所示：/ i. h' Q$ J9 q" o
, i( J- h  B8 W5 s8 T! c! n
    //O(n)wherenisthenumberoftokenholderswithstake
1 R- Z9 o# Z* F! A; Q/ ^" y) n* p! f8 `9 Y, w% M
    for(uinti=0;i
' }  j7 p) ^5 ^( k" P9 R) ^" M
6 N7 t' `- x6 |$ I- k$ `1 a$ D    if(currentDrawnNumber.segmentEnd)2 W8 O* |2 G2 k' k
9 H& P* L+ o! B0 n3 }
    returntokenHolders.address
3 G; O8 }9 u& d; ~) q
6 C  g! }, p; U+ J) P    在任何规模可观的系统中，每次抽奖都会需要很多算力。这种算法还制造了O（d*a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。
; i& j" P- A' U5 m
1 w; w7 t4 |' _# O* e- j& x" W    树状数组解决方案, X2 p* ]% T5 x0 {2 V: ]- ]

: a% N8 k) d6 _6 I: t6 T    在寻求更好的方法过程中，我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组（K=2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：0 h6 F3 D: t7 ^
! |) z+ n, v6 q. E6 q
    二进制树状数组示例
) J6 N9 s1 f2 r, N1 d0 V5 ^
* e0 l6 B. L7 `9 b9 S8 l    在以上示例中，假设我们抽取到数字13，寻取方式如下：首先13落在[0-24,25-49]的哪个区？0-24，所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。7 P7 m" ]# {: P- ]3 B9 x

& ]( D, J, c5 R' _& F* X    现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。
9 M3 H4 q! W" t! _$ Z
7 L# M/ u* y0 W1 x$ s6 h' ~& S    所以这个数据结构让我们的抽取复杂度变为O（K*log（n）/log（K）），其中K是每个节点的子节点数。log（n）/log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。
: N3 M0 }) l: b+ ]' E) B4 y* q& ~% \3 M- a. {8 ^
    设置，删除和追加的复杂度都是O（log（n）/log（K）），因为是从给定的数据节点开始，逐级向上操作。注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现：
- b1 j( c. O  w5 V4 d$ K
: C4 w1 D1 s# i  N5 F" d8 k    设置：设置新值并更新根值。: E7 H9 m4 E$ E: G) N& Y* ^1 v/ \3 Y

+ V+ w* B% h3 e1 ~( t# h) S) r% f    删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。# R, b  {- n! i* F2 F, @
, c  A5 S# }' Y
    追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。2 k' Q0 R3 Q# J3 U, `+ k

: e: Q/ E4 \# z$ F1 S    执行过程中的算力节省
1 S9 Q, z+ {1 y7 j3 M0 J
2 w: u! ^6 h$ O    因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示，列表会是：[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历：
, n. @1 i+ J. }% q: ]6 V1 {: N# s. T5 b/ }9 I! z
    节点i的第C个子节点：K*i+c。原理：首先必须跳过每个i之前的节点的和它们的子节点，所以是K*i；然后加上c来得到你想要的子节点。
' _& h1 r8 m2 j+ ]
% {5 Y" H9 c. p. L4 ?0 c    节点i的根节点：（i-1）/K。原理：跳过多少个拥有K个子节点的节点才能到达i。: u5 Y: E8 S9 Y2 ~: L

  u  e5 H* E5 X% Q) J2 k! [    检查节点i是否是第一个/最左边的节点：（i-1）％K===0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。4 }1 v; W- p) V9 O
+ h; _8 p) M$ J, e
    Kleros的实例
+ ~! s2 `3 k- b% [: {) i- Z( J0 C: G1 O! i# z6 e  o* F
    Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros ... cts/data-structures
; |2 A3 Y( V2 e( G/ }3 |
- B" d7 j& v, p4 s' c$ |  c# P    里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。