如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案......, {9 m1 U9 m  ^7 P  H" r

1 f, f& l( A$ M) D. q1 v    在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量，这就非常简单。但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......
9 k1 i7 ^9 e2 n+ r: }) w0 @. `  e) G# I( U" y9 ^5 h
    基本的方式
2 u4 [! L' ~  d
) E9 k. U  `) u1 `- Z# G! Z& v6 `    构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：  C7 Z" n/ E- Q

: T5 Q5 c6 P2 a$ z( m    tokenHolder.segmentStart=segmentSize;# r# t5 }8 e7 A+ R- n, d5 d: M

" _# r0 K) F" }+ a. E# d    segmentSize+=_stake;
, m, p7 L" `' k% ^9 h+ r; w; v; ^& ?4 v8 l+ j! n
    tokenHolder.segmentEnd=segmentSize;+ }& B' j9 Z1 H6 [; Z) f2 \

$ P) h' {; I8 \: g. V8 g& @5 ^    这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。
7 O& U+ C4 @. N4 L5 B
; x9 ^: a/ }. L4 n6 p    首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。. t  [' L! @3 D# W, r% T& o
5 F, E- `8 ]9 S
    其次，获得被抽中者需要迭代每位持有者，如下所示：
# F0 a0 |2 x! k# b( G" u% b$ {. {
    //O(n)wherenisthenumberoftokenholderswithstake
: b8 e% p1 C1 h0 T# g" }, b5 C0 a) e& u
    for(uinti=0;i: p7 x, ^; o. j; M7 T* I6 q" m- P
2 @& t2 g; x& s' k) N! y& D! F
    if(currentDrawnNumber.segmentEnd)) }& K5 i& X  @

6 v, k0 g6 u3 Y    returntokenHolders.address% l+ F; _+ o( @# Z9 f% ]  o
3 D. o; S, Y! ?
    在任何规模可观的系统中，每次抽奖都会需要很多算力。这种算法还制造了O（d*a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。& Y: }8 D! k8 N0 x6 s/ n/ ~, V

% j" b: ], J: M/ b; n# N    树状数组解决方案
# O( i% y& Y! s' b! P( ?/ B5 `
- E. a* B9 R7 y! b! v4 k    在寻求更好的方法过程中，我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组（K=2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：- V1 J1 j- L  C3 ~. M
; C/ Z0 \+ `( n$ y  G
    二进制树状数组示例; x( _5 R& P6 z
' B9 h! w9 J' y, g3 U6 J' y3 j
    在以上示例中，假设我们抽取到数字13，寻取方式如下：首先13落在[0-24,25-49]的哪个区？0-24，所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。5 d& Z% \0 m$ s2 O  {6 H8 ?
. U3 b0 Q4 [: A& e
    现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。
+ ]  U6 Y' n& Y- J; s
. o) q+ n8 @& C+ c    所以这个数据结构让我们的抽取复杂度变为O（K*log（n）/log（K）），其中K是每个节点的子节点数。log（n）/log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。! E0 j* V2 W! H5 F$ [0 @$ a" Q
! n, L" K$ @: y# z
    设置，删除和追加的复杂度都是O（log（n）/log（K）），因为是从给定的数据节点开始，逐级向上操作。注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现：
$ {1 K# o6 ?% D! p5 i1 Q7 I" l0 L+ ^1 m+ M6 h* p
    设置：设置新值并更新根值。
. c0 j9 K! s7 r; W! Q3 {' x2 F' t& Q7 {5 H. y; T
    删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。
2 P! P* s/ S# X2 X$ z2 c3 t# \  ^  y7 P) ]% V; a! Y! s* a
    追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。
( G9 I) [. [% R  Z; R/ G
$ I8 b( e. p  V/ d    执行过程中的算力节省5 m8 C  Z; U; a8 ^; y8 e

' S( m& v# W0 c  p. G" U$ Q, K    因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示，列表会是：[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历：- d  M3 K7 O3 e- b1 F4 f; a/ r

" ~  }' t$ B$ x8 P3 y    节点i的第C个子节点：K*i+c。原理：首先必须跳过每个i之前的节点的和它们的子节点，所以是K*i；然后加上c来得到你想要的子节点。
" S  m. l3 S% d9 C( N9 w8 j2 j! e  S2 u% m6 Z
    节点i的根节点：（i-1）/K。原理：跳过多少个拥有K个子节点的节点才能到达i。
& X/ d/ d& u. o2 L. q) F3 |2 f* q' Z
; p1 Q% A/ F( w1 w4 j: [$ ^    检查节点i是否是第一个/最左边的节点：（i-1）％K===0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。
0 P1 F$ R# M( k0 U* M1 c: ]/ {8 ?% G8 b- W9 c1 |0 j3 F
    Kleros的实例( \  f- y5 `, Z4 o5 j
4 q+ T( V; I4 |
    Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros ... cts/data-structures
; c. K, `! ^1 q4 }, w2 K( B
3 l6 O9 o% s* m, _6 i6 H    里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。